盛最多水的容器（LeetCode 11）

问题简介

🔗 LeetCode 中文链接

题目描述

给定一个长度为 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

示例 3：

输入：height = [4,3,2,1,4]
输出：16

---

解题思路

✅ 双指针法（最优解）

这是一个经典的双指针问题。核心思想是：

• 初始时，左指针 l = 0，右指针 r = n - 1，此时宽度最大。
• 容器的面积由 较短的那条边 决定（短板效应）。
• 每次移动 较短边 对应的指针，因为：
  • 如果移动较长边，宽度减小，高度不会超过当前短板，面积只会更小；
  • 移动短板，虽然宽度减小，但可能遇到更高的板，从而获得更大的面积。

步骤如下：

1. 初始化 l = 0, r = n - 1, maxArea = 0。
2. 当 l < r 时循环：
   • 计算当前面积：area = (r - l) * min(height[l], height[r])
   • 更新 maxArea = max(maxArea, area)
   • 若 height[l] < height[r]，则 l++；否则 r--
3. 返回 maxArea

❌ 暴力法（不推荐）

双重循环枚举所有 (i, j) 组合，计算面积并取最大值。

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 在 LeetCode 上会超时（TLE）

💡 因此我们只实现双指针法。

---

代码实现

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int maxArea = 0;
        
        while (l < r) {
            int width = r - l;
            int h = Math.min(height[l], height[r]);
            maxArea = Math.max(maxArea, width * h);
            
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        
        return maxArea;
    }
}

func maxArea(height []int) int {
    l, r := 0, len(height)-1
    maxArea := 0

    for l < r {
        width := r - l
        h := height[l]
        if height[r] < h {
            h = height[r]
        }
        area := width * h
        if area > maxArea {
            maxArea = area
        }

        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }

    return maxArea
}

---

示例演示

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

步骤	l	r	height[l]	height[r]	宽度	高度	面积	maxArea
初始	0	8	1	7	8	1	8	8
1	1	8	8	7	7	7	49	49
2	1	7	8	3	6	3	18	49
3	1	6	8	8	5	8	40	49
4	2	6	6	8	4	6	24	49
…	…	…	…	…	…	…	…	49

最终返回 49。

---

答案有效性证明

关键性质：
在任意时刻，若 height[l] <= height[r]，则对于当前 l，其与任何 j ∈ (l, r] 构成的容器面积都不会超过当前 (l, r) 的面积。

证明：

• 宽度：j - l < r - l
• 高度：min(height[l], height[j]) <= height[l]
• 所以面积 < (r - l) * height[l]，即当前面积已是 l 能达到的最大值。

因此，l 可以安全地向右移动，无需再考虑它与其他右侧柱子的组合。

同理适用于 height[r] < height[l] 的情况。

由此可知，双指针法不会遗漏最优解。

---

复杂度分析

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

• 双指针法只需一次遍历，每个元素最多被访问一次。
• 仅使用常数额外空间。

---

问题总结

• ✅ 核心思想：短板效应 + 贪心策略。
• ✅ 关键洞察：移动短板才有可能获得更大面积。
• ✅ 算法选择：双指针法是最优解，简洁高效。
• 💡 适用场景：涉及“两端”、“区间”、“面积/乘积最大化”且具有单调性或可剪枝性质的问题。

📌 记住：当看到“最大面积”、“两边界”、“数组两端”等关键词时，优先考虑双指针！

github地址: https://github.com/swf2020/LeetCode-Hot100-Solutions