盛最多水的容器：双指针贪心的严格数学证明

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

---

开篇故事

LeetCode 11 是我最喜欢用来讲"算法正确性"的题目之一。这道题的双指针解法只有六七行代码，但背后的贪心正确性证明，是很多学算法的人最容易忽略的地方。

我见过很多人能写出这道题的双指针代码，但被追问"为什么每次移动较短的那侧"时，就开始支支吾吾。"因为移动较长的那侧没用？"——这句话方向对，但说的不够严格。

面试官想听到的是：当 height[lo] <= height[hi] 时，固定 lo、移动 hi 到任何其他位置，都不可能比当前更优——所以移动 hi 是无效操作，可以安全跳过；唯一的希望是移动 lo，因为有机会遇到更高的左边界。这才是严格的贪心论证。

---

一、题目解析

题目（LeetCode 11）： 给定 n 个非负整数 a1, a2, ..., an，其中每个数代表坐标中的一个点 (i, ai)。画 n 条垂线，第 i 条线的端点在 (i, 0) 和 (i, ai)。找出其中两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

容积公式：area(i, j) = min(height[i], height[j]) * (j - i)

示例：

• height = [1,8,6,2,5,4,8,3,7]，输出：49（取 height[1]=8 和 height[8]=7，面积 = 7*7 = 49）

---

二、解法一：暴力枚举 O(n²)

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

复杂度分析

• 时间复杂度：O(n²)。双重循环。
• 空间复杂度：O(1)。

---

三、解法二：分治（了解即可）

先找到最高的柱子，以它为分界，分别在左半和右半找最优解，再合并。但这种方法实现复杂，且时间复杂度仍是 O(n log n)，不如双指针，这里不展开。

---

四、解法三最优：双指针贪心 O(n)

贪心策略

双指针：lo 从最左，hi 从最右。每步移动较矮的那侧。

为什么？严格证明如下：

设当前状态为 (lo, hi)，且 height[lo] <= height[hi]（lo 较矮）。

当前容积 = height[lo] * (hi - lo)。

我们要证明：在这种状态下，hi-- 是安全的，即以 hi 为右边界的所有更优解都已经被考虑过了。

等价地，我们证明：area(lo, hi) 已经是所有以 lo 为左边界的容器中最大的。

• 对任何 j < hi：area(lo, j) = min(height[lo], height[j]) * (j - lo) <= height[lo] * (j - lo) <= height[lo] * (hi - lo) = area(lo, hi)。

所以以 lo 为左边界，hi 是最优右边界（宽度最大，且高度被 lo 决定）。lo 左边界固定时，hi-- 不可能找到更优解。

因此可以安全地 lo++，放弃 lo 作为左边界。

同理： 当 height[lo] > height[hi] 时，hi-- 是安全的。

移动策略总结： 每步移动较矮的那侧（因为保留较矮侧已经是最优，没有任何提升空间了）。

Mermaid 图：双指针移动决策

完整代码

public class Solution3 {
    public int maxArea(int[] height) {
        int lo = 0, hi = height.length - 1;
        int maxWater = 0;

        while (lo < hi) {
            // 计算当前容积
            int water = Math.min(height[lo], height[hi]) * (hi - lo);
            maxWater = Math.max(maxWater, water);

            // 移动较矮的那侧（短板决定容积上限，换掉短板才有提升空间）
            if (height[lo] <= height[hi]) {
                lo++;
            } else {
                hi--;
            }
        }

        return maxWater;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(sol.maxArea(new int[]{1,8,6,2,5,4,8,3,7})); // 49
        System.out.println(sol.maxArea(new int[]{1,1})); // 1
        System.out.println(sol.maxArea(new int[]{4,3,2,1,4})); // 16
        System.out.println(sol.maxArea(new int[]{1,2,1})); // 2
    }
}

复杂度分析

• 时间复杂度：O(n)。lo 和 hi 各移动最多 n 次，总移动次数 <= n-1 次。
• 空间复杂度：O(1)。

---

五、举一反三

题号	题目	双指针类型
167	两数之和 II	对撞指针，找和
42	接雨水	双指针 + 动态规划，更复杂
15	三数之和	排序后对撞指针
977	有序数组的平方	从两端向中间归并

对撞指针模板（最大化/最小化某个值）：

int lo = 0, hi = n - 1;
int result = 0;
while (lo < hi) {
    int cur = compute(arr, lo, hi);  // 计算当前状态
    result = Math.max(result, cur);  // 或 Math.min
    if (shouldMoveLo(arr, lo, hi)) {
        lo++;
    } else {
        hi--;
    }
}

---

六、踩坑实录

坑一：移动等高的情况

当 height[lo] == height[hi] 时，移动哪侧都可以。但要注意两种写法的一致性：

• if (height[lo] <= height[hi]) lo++;（等高时移动 lo）
• if (height[lo] < height[hi]) lo++; else hi--;（等高时移动 hi）

两种写法都正确，但不能写成"等高时两端都移动"然后没有 else，因为那样可能跳过答案。

坑二：在更新 maxWater 后立即移动，而不是先计算再移动

有人把计算 water 放到了 if-else 分支里面，只在某些情况下更新 maxWater，这样会漏掉一些情况。正确做法是：每次循环先计算当前容积更新 maxWater，再决定移动哪侧。

坑三：认为可以优先移动靠近中间的指针

有人觉得"中间的柱子可能更高，先移向中间"，这是错误的。贪心的核心是"短板决定一切，换短板"，不是"靠近中间"。这个错误的直觉会导致代码无法保证正确性。

坑四：与接雨水（42）的方法混淆

接雨水问题和盛水容器是完全不同的题目。接雨水是计算柱子之间能接住多少雨水，需要对每个位置计算左右最大高度，解法更复杂。不要把两道题的代码混着用。

---

七、总结

这道题教会了我一件事：双指针的贪心策略必须有严格的证明支撑，不能只靠直觉。

证明的核心是：在当前状态，以较矮的那侧为固定边界，无论另一侧怎么移动，都不可能找到更大的容积（因为宽度减小，高度又被矮侧限制）。因此可以安全排除矮侧作为边界的所有可能，移动矮侧指针。

这个"安全排除"的逻辑，和二分查找的"每步减半搜索空间"是同一种思维，只是应用场景不同。