题目描述

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

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

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

说明：你不能倾斜容器。

示例

示例 1：

输入：[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⁵
• 0 <= height[i] <= 10⁴

---

题型属于

• 双指针
• 数组
• 贪心

---

解题思路：双指针 + 贪心

思路说明

这道题的核心是：如何高效地找到最大面积。

暴力解法不可行

枚举所有两两组合 → O(n²) → 10⁵ 规模会超时。

双指针贪心思想

容器面积取决于两个因素：

• 宽度：r - l（两指针距离）
• 高度：min(height[l], height[r])（较矮的那条线）

        │
        │     │
   │    │     │     │
   │    │  ×  │     │        ← 容器：宽 × 高
   │    │  ×  │     │
   │    │  ×  │     │
───┴────┴────┴────┴───────
   l              r

关键洞察：宽度越大、高度越高，面积越大。

为什么移动短的那条？

假设 height[l] < height[r]：

当前面积 = (r - l) × min(height[l], height[r]) 
         = (r - l) × height[l]  （因为 height[l] 更短）

如果把 l（短的那条）向右移动：

• 宽度肯定减小
• 新高度 height[l'] 可能是更大或更小
• 但无论如何，面积不会比现在更大，因为高度取决于短板

所以：移动短的那条线，才有可能找到更大的面积。

代码实现（C++）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;                          // 左指针
        int r = height.size() - 1;          // 右指针
        int maxArea = 0;                     // 最大面积
        
        while (l < r) {
            int width = r - l;              // 宽度
            int h = min(height[l], height[r]); // 高度（取短板）
            maxArea = max(maxArea, width * h);  // 更新最大面积
            
            // 移动短的那条线
            if (height[l] < height[r]) {
                l++;                         // 左边更短，移动左边
            } else {
                r--;                         // 右边更短（或相等），移动右边
            }
        }
        
        return maxArea;
    }
};

复杂度分析

复杂度	值
时间复杂度	O(n)，双指针各遍历一次
空间复杂度	O(1)，原地操作

正确性证明（简要）

1. 初始状态：左右指针分别指向两端，涵盖所有可能的容器
2. 每一步决策：只移动短的那条线，原因如上分析
3. 遍历结束：双指针相遇，所有情况都已枚举
4. 最优解保证：每次迭代都记录当前最大面积，最终返回的必为全局最优

---

图解过程

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

步骤    l   r   width  height  area  操作
初始    0   8    8      1      8     移动 l（更短）
2       1   8    7      8      56    移动 r（更短）
3       1   7    6      8      48    移动 r
...（继续直到相遇）
最终结果: 49

---

学习总结

✅ 关键点：

• 双指针从两端向中间收敛
• 短板效应：容器高度由最短边决定
• 移动短边可能找到更大面积，移动长边一定不会

✅ 面试常考点：

• 双指针模板
• 贪心思想证明
• 时间复杂度分析

✅ 易错点：

• 不能只移动一条边，要动态调整
• 理解为什么移动短边而不是长边