最大容量问题
Question
输入一个数组
容器的容量等于高度和宽度的乘积(面积),其中高度由较短的隔板决定,宽度是两个隔板的数组索引之差。
请在数组中选择两个隔板,使得组成的容器的容量最大,返回最大容量。示例如下图所示。
容器由任意两个隔板围成,因此本题的状态为两个隔板的索引,记为
根据题意,容量等于高度乘以宽度,其中高度由短板决定,宽度是两隔板的数组索引之差。设容量为
设数组长度为
贪心策略确定
这道题还有更高效率的解法。如下图所示,现选取一个状态
如下图所示,若此时将长板
这是因为在移动长板
反向思考,我们只有向内收缩短板
由此便可推出本题的贪心策略:初始化两指针,使其分列容器两端,每轮向内收缩短板对应的指针,直至两指针相遇。
下图展示了贪心策略的执行过程。
- 初始状态下,指针
和 分列数组两端。 - 计算当前状态的容量
,并更新最大容量。 - 比较板
和 板 的高度,并将短板向内移动一格。 - 循环执行第
2.
步和第3.
步,直至 和 相遇时结束。
代码实现
代码循环最多
变量
Text Only | |
---|---|
1 |
|
正确性证明
之所以贪心比穷举更快,是因为每轮的贪心选择都会“跳过”一些状态。
比如在状态
观察发现,这些被跳过的状态实际上就是将长板
以上分析说明,移动短板的操作是“安全”的,贪心策略是有效的。
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用