📝 题目描述

给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

示例1

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例2：

输入：height = [1,1]
输出：1

提示

• n == height.length

• 2 <= n <= 10^5

• 0 <= height[i] <= 10^4

---

 解题思路

核心理解

容器的盛水量由 两条线中较短的那条 和 两条线之间的距离 决定：

text

水量 = min(height[left], height[right]) × (right - left)

我们的目标是找到使这个值最大的 (left, right) 对。

方法一：暴力法（不推荐）

java

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            int area = Math.min(height[i], height[j]) * (j - i);
            max = Math.max(max, area);
        }
    }
    return max;
}

• 时间复杂度：O(n²)

• 空间复杂度：O(1)

• ❌ 对于 n = 10^5 会超时

方法二：双指针（贪心） 最优解

核心思想

使用两个指针分别指向数组的 两端，每次计算当前水量后，移动较短的那条线 的指针。

为什么移动较短的那条？

关键在于：容器的水量取决于较短的边。

• 如果移动较长的边，宽度减小，高度最多不变（取较短边），水量一定减少

• 如果移动较短的边，虽然宽度减小，但高度有可能变大，水量可能增加

所以我们每次都“舍弃”较短的边，向内移动指针，这样不会错过最优解。

图解示例

以 [1,8,6,2,5,4,8,3,7] 为例：

text

初始：left=0(1), right=8(7)
水量 = min(1,7) × 8 = 8
移动 left（因为1<7）→ left=1(8)

left=1(8), right=8(7)
水量 = min(8,7) × 7 = 49
移动 right（因为7<8）→ right=7(3)

left=1(8), right=7(3)
水量 = min(8,3) × 6 = 18
移动 right → right=6(8)

left=1(8), right=6(8)
水量 = min(8,8) × 5 = 40
移动 left 或 right 均可 → left=2(6)

... 继续直到 left >= right
最大值 = 49

代码实现

java

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // 计算当前面积
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);
            
            // 移动较短的那一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

小优化：跳过相同高度的线

java

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, h * (right - left));
            
            // 跳过所有不高于当前高度的线
            while (left < right && height[left] <= h) left++;
            while (left < right && height[right] <= h) right--;
        }
        
        return maxArea;
    }
}

---

 复杂度分析

方法	时间复杂度	空间复杂度
暴力法	O(n²)	O(1)
双指针	O(n)	O(1)

---

验证示例

java

public static void main(String[] args) {
    Solution solution = new Solution();
    
    int[] height1 = {1,8,6,2,5,4,8,3,7};
    System.out.println(solution.maxArea(height1)); // 输出: 49
    
    int[] height2 = {1,1};
    System.out.println(solution.maxArea(height2)); // 输出: 1
}

---

 关键点总结

1. 面积公式：min(left, right) × 距离

2. 双指针初始化：一左一右

3. 移动策略：每次都移动较短的边

4. 正确性保证：移动长边一定不会得到更优解

5. 时间复杂度：O(n)，一次遍历即可