---

前言

在计算机科学的世界里，有些问题看似简单，却蕴含着深刻的算法思想。LeetCode 第 11 题「盛最多水的容器」便是这样一道经典题目。它以一个直观的生活场景——选择两根柱子构成容器盛水——作为切入点，考察我们对数组操作、数学建模以及算法优化的综合能力。

---

一、题目回顾

给定一个长度为 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 <= 105
0 <= height[i] <= 104

---

二、整体思路

2.1 暴力法（不可行）

最直观的解法是枚举所有可能的两条线组合，计算面积并取最大值。这需要两层循环，时间复杂度为 O(n²)，当数组长度很大时（题目中 n 可达 10^5）会超时。因此我们需要更优的解法。

2.2 观察：面积由什么决定？

容器面积由两个因素决定：

• 宽度：两根柱子之间的距离 (j - i)
• 高度：两根柱子中较短的那一根的高度（因为水会从矮的一边溢出）

所以公式可以写成：
面积 = 宽度 × 较矮高度

2.3 直觉：从最宽的开始尝试

既然宽度对面积有贡献，我们不妨从宽度最大的容器开始考虑——也就是最左边和最右边的两根柱子（i=0, j=n-1）。此时宽度最大，但高度可能很小。
接下来，我们需要缩小宽度（即移动其中一个指针）来寻找可能更高的柱子，以期获得更大的面积。

问题来了：应该移动左边的指针，还是右边的？

2.4 核心推理：移动较矮的那一边

假设当前左指针指向柱子 L（高度 hL），右指针指向柱子 R（高度 hR），当前面积为 (R-L) × min(hL, hR)。

无论移动哪个指针，宽度都会减少 1。但面积是否会增大，取决于较矮高度的变化。

情况一：左边较矮（hL < hR）

• 如果移动右边（较高柱子）：新右边的高度可能更高、相等或更低，但容器的高度仍然受限于左边的 hL（因为左边没变）。所以新高度 ≤
  hL，而宽度变小了，新面积一定小于当前面积。

结论：移动较高的一边永远得不到更大的面积。

• 如果移动左边（较矮柱子）：新左边的高度可能变高（遇到更高的柱子），此时新容器的高度可能变为 min(新hL, hR)，有可能超过原来的
  hL，从而有可能弥补宽度的损失，使面积增大。

结论：移动较矮的一边才有机会获得更大面积。

情况二：右边较矮（hR < hL）

同理，应该移动右边的指针（较矮的那边）。

情况三：两边相等（hL == hR）

此时移动任意一边，新高度都不会超过当前高度，宽度减小，面积一定不会变大。所以移动哪边都可以，不影响最终结果。

2.5 算法步骤

基于以上推理，我们可以采用双指针法：

• 初始化左指针 i = 0，右指针 p = height.length - 1，最大面积 max = 0。

• 当 i < p 时循环：

  • 计算当前面积 area = (p - i) * Math.min(height[i], height[p])

  • 用 area 更新 max

  • 如果 height[i] < height[p]，则 i++（移动较矮的左边）；否则 p–（移动较矮的右边）

• 循环结束后返回 max。

2.6 为什么不会错过最优解？

我们可以这样理解： 假设最优解对应的两根柱子是 (i*, j*)。在指针移动过程中，当左指针到达 i* 而右指针还在 j* 右边时（或右指针到达 j* 而左指针还在 i* 左边时），根据我们的规则，我们一定会保留较高的那一边，而移动较矮的一边，直到另一个指针也到达最优边界。这个过程保证了我们最终会遍历到 (i*, j*) 这个组合，从而不会遗漏最优解。

---

三、预备知识

3.1 数组的基本操作

• 数组是连续内存空间，可以通过下标 O(1) 访问元素。
• 本题中我们只需要读取高度，不需要修改数组。

3.2 双指针技巧

• 双指针通常用于在有序或无序数组中，通过两个指针的相向或同向移动，将时间复杂度从 O(n²) 降到 O(n)。
• 本题使用的是左右指针：一个指向数组开头，一个指向结尾，然后根据某种条件移动其中一个指针。

3.3 面积计算

• 面积由两个因素决定：宽度（两指针的距离）和高度（两指针所指高度的较小值）。
• 目标是最大化宽度与高度的乘积。

---

四、代码实现（Java 解法）

4.1 正确代码

class Solution {
    public int maxArea(int[] height) {
        int res = 0;                // 记录最大面积
        int i = 0;                  // 左指针
        int p = height.length - 1;  // 右指针
        
        while (i < p) {             // 当两指针未相遇时
            // 计算当前面积：宽度 × 较小高度
            int area = (p - i) * Math.min(height[i], height[p]);
            // 更新最大面积
            res = Math.max(res, area);
            
            // 移动较矮的那一边的指针
            if (height[i] < height[p]) {
                i++;    // 左指针右移
            } else {
                p--;    // 右指针左移
            }
        }
        return res;
    }
}

4.2 关键决策：if (height[i] < height[p]) { i++; } else { p–; }

总是移动较矮的那一边的指针。因为较矮的一边限制了当前面积，移动它才有可能遇到更高的边，从而增加面积。如果两边相等，移动任意一边均可（代码中归为 else 移动右指针）。

---

五、总结

LeetCode 11 题是一道非常经典的双指针入门题，它简洁而优美地展示了如何通过数学推理优化算法。

5.1 核心要点

• 双指针法通过一次遍历找到最大面积，时间复杂度 O(n)。
• 每次移动较矮的指针，是保证不遗漏最优解的关键。
• 面积由宽度和较小高度决定，移动指针后宽度减小，只有提高较小高度才有可能增大面积。

5.2 常见错误与注意事项

(1)指针移动条件理解错误
为什么要移动较矮的边？如果移动较高的边，会不会错过更大面积？
解释： 假设当前左矮右高，如果移动较高的右边，那么新的面积高度不会超过原来的矮边（因为矮边没变），但宽度减少了，所以面积必然减小。因此移动较高的边只会得到更小的面积，不可能得到更大的。所以只能移动较矮的边。
(2)数组下标越界
循环条件 i < p 确保了在访问 height[i] 和 height[p] 时不会越界。因为 i 从 0 开始，p 从 length-1 开始，且每次只移动一步，不会出现 i 超过 p 或 p 小于 0 的情况。