1.题目介绍
2.题解（双指针）
参考文章：
作者：Krahets
链接：https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
来源：力扣（LeetCode）
思路
设两指针 \(i,j\) ,指向的水槽板高度分别为 \(h[i]\) ,\(h[j]\) , 此状态下水槽面积为 \(S(i,j)\) 由于可容纳水的高度由两板中的 短板 决定,因此可得如下 面积公式 \(\vdots\)
\[S(i,j)=min(h[i],h[j])\times(j-i) \]
在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽 （底边宽度 -1） 变短:
- 若向内 移动短板, 水槽的短板 \(min(h[i],h[j])\) 可能变大, 因此下个水槽的面积可能增大。
- 若向内 移动长板, 水槽的短板 \(min(h[i],h[j])\) 不变或变小,因此下个水槽的面积 一定变小。
明白这一点的同时，双指针的思路也就跃然纸上了，分别在最左段和最右端设置两个双指针，记录下每次运算后最大的水槽面积，之后向内移动短板（移动长板，面积肯定变小，是无用组合，可以舍弃），最后知直到两指针重合。
算法流程:
- 初始化: 双指针 \(i,j\) 分列水槽左右两端;
- 循环收窄: 直至双指针相遇时跳出;
a. 更新面积最大值 \(res\) ,
b.选定两板高度中的短板, 向中间收窄一格; - 返回值: 返回面积最大值 \(res\) 即可;
正确性证明
若暴力枚举, 水槽两板固成面积 \(S(i,j)\) 的状态总数为 \(C(n,2)\) 。
假设状态 \(S(i,j)\) 下 \(h[i]<h[j]\) ,在向内移动短板至 \(S(i+1,j)\) ,则相当于消去了
\(S(i,j-1),S(i,j-2),...,S(i,i+1)\) 状态集合。而所有消去状态的面积一定都小于当前面积(即 \(<S(i,j))\) ,因为这些状态:
- 短板高度: 相比 \(S(i,j)\) 相同或更短 (即 \(\leq h[i]\) );
- 底边宽度: 相比 \(S(i,j)\) 更短;
因此,每轮向内移动短板,所有消去的状态都不会导致面积最大值丢失,证毕。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1;
int res = 0;
while (i < j){
res = height[i] <= height[j] ? std::max(res, (j - i) * std::min(height[i++], height[j])) : std::max(res, (j - i) * std::min(height[i], height[j--]));
}
return res;
}
};