11. 盛最多水的容器
3 min
题目
思路
核心思想是使用双指针从数组两端向中间移动，每次移动高度较小的指针。
正确性证明：容器容量由较短的边和宽度共同决定。移动较短的指针可能遇到更高的边，从而弥补宽度减少的损失；而移动较长的指针时，新边高度不会超过原较短边（甚至可能更小），且宽度必然减少，因此不可能获得更大容量。
- Step 1: 初始化左指针l=0，右指针r=n-1，计算初始面积
- Step 2: 当l<r时循环，比较height[l]和height[r]
- Step 3: 移动高度较小的指针（若相等则移动左指针）
- Step 4: 每次移动后计算新面积并更新最大值
- Step 5: 循环结束返回最大面积
复杂度
- 时间复杂度: ，双指针仅遍历数组一次，比较操作为线性时间瓶颈。
- 空间复杂度: ，仅使用固定数量的指针和变量，无额外空间消耗。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0,r = height.size()-1;
int area = min(height[l],height[r])*(r-l);
while(l < r){
if(height[l] > height[r]){
r--;
}
else
l++;
area = max(min(height[l],height[r])*(r-l),area);
}
return area;
}
};