Leetcode 11. Container With Most Water（接最多水的容器）

问题理解

给定一个长度为 n 的整数数组 height，表示在坐标 (i, 0) 到 (i, height[i]) 处画一条竖直线。选择两条线，与 x 轴构成一个容器，使其能装最多的水（不能倾斜）。求 最大储水量。

容器面积 = 两线间距 × 较短线的高度即：area = (j - i) * min(height[i], height[j])

思路

• 容器的 面积 = 两线之间距离 × 较短的那条线的高度。
• 初始时，左右指针分别在数组两端（i=0, j=n-1），此时宽度最大。
• 每次移动 较短的那一边 的指针：
  • 因为面积受限于较短边，只有换掉它，才有可能得到更大的面积；
  • 如果移动较高的边，宽度变小，高度不会超过当前较短边，面积一定不会更大。

算法步骤：

1. 初始化 left = 0, right = n - 1, max_area = 0
2. 当 left < right 时循环：
   • 计算当前面积：(right - left) * min(height[left], height[right])
   • 更新 max_area
   • 如果 height[left] < height[right]，则 left++
   • 否则 right--
3. 返回 max_area

Code

class Solution {
public:int maxArea(vector<int>& height) {int i = 0, j = height.size() - 1;int max_contain = 0;while(i < j){int area = (j - i) * min(height[i], height[j]);if(area > max_contain) max_contain = area;else if(height[i] < height[j]) i++;else j--;}return max_contain;}
};