04 对撞指针进阶：盛水容器与接雨水的几何直觉

对撞指针进阶：盛水容器与接雨水的几何直觉

摘要

Container With Most Water 和 Trapping Rain Water 是对撞指针中正确性最难直觉证明的两道题。前者的关键在于证明”短板方移动不会错过最优解”；后者有单调栈、前后缀预处理、对撞指针三种解法，本文重点分析对撞指针解法与前后缀预处理解法的等价性。理解这两道题的几何直觉，是对撞指针算法理解从”会用”到”会证”的重要跨越。

---

第 1 章 LeetCode 11：盛最多水的容器

1.1 题目

LeetCode 11 - Container With Most Water（中等）

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

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

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

说明： 你不能倾斜容器。

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

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

1.2 水量的计算公式

两条线 height[left] 和 height[right] 围成的容器，水量为：

$\text{water}(left,right)=\min (\text{height}[left],\text{height}[right])\times (right-left)$

• 宽度：$right-left$（两条线的距离）
• 高度：$\min (\text{height}[left],\text{height}[right])$（短板决定高度，水不能超过短板）

暴力解法：枚举所有 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 对 (left, right)，计算水量取最大值，$O(n^2)$。

1.3 对撞指针解法

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;
 
    while (left < right) {
        int water = Math.min(height[left], height[right]) * (right - left);
        maxWater = Math.max(maxWater, water);
 
        // 移动短板：短板那侧向内收缩
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;  // 相等时移动哪侧都可以
        }
    }
    return maxWater;
}

时间复杂度：$O(n)$；空间复杂度：$O(1)$。

1.4 正确性证明：为什么移动短板不会错过最优解？

这是面试中最常被追问的问题，也是最容易用直觉回答而答不到点子上的问题。

命题：当 height[left] < height[right] 时，执行 left++，不会漏掉任何以 left 为左端点的更优解。

证明：

当前 left 和 right 组合的水量是 $\text{height}[left]\times (right-left)$。

考虑以 left 为左端点、任意 right' < right 为右端点的组合：

$\text{water}(left,righ{t}^{\prime })=\min (\text{height}[left],\text{height}[righ{t}^{\prime }])\times (righ{t}^{\prime }-left)$

因为 $righ{t}^{\prime }<right$，宽度 $righ{t}^{\prime }-left<right-left$。

高度 $\min (\text{height}[left],\text{height}[righ{t}^{\prime }])\le \text{height}[left]$（取 min 不会超过 height[left]）。

因此： $\text{water}(left,righ{t}^{\prime })\le \text{height}[left]\times (righ{t}^{\prime }-left)<\text{height}[left]\times (right-left)=\text{water}(left,right)$

即：以 left 为左端点、任意比当前 right 更靠左的右端点的组合，水量都不如当前 (left, right) 的水量。

结论：在执行 left++ 之前，我们已经计算了 water(left, right)，且以 left 为左端点的所有其他组合的水量均 $\le$ water(left, right)，可以安全地排除 left，将 left++。$\square$

设计哲学：短板的局限性是排除的依据

移动短板的直觉是：当前水量的瓶颈是短板（height[left]），不管右端 height[right] 有多高，水都无法超过 height[left]。所以即使 right 移动，以当前 left 为左端点的水量上界就是 height[left] * (当前宽度)——而当前宽度已经是最大的了。移动 left，才有可能找到更高的左板，突破瓶颈。

为什么两板等高时移动哪边都可以？

当 height[left] == height[right] 时，设高度为 $h$。以 left 为左端点、right' < right 为右端点：

$\text{water}(left,righ{t}^{\prime })\le h\times (righ{t}^{\prime }-left)<h\times (right-left)$

同理，以 right 为右端点、left' > left 为左端点的水量也不超过当前。所以移动任意一端都不会错过更优解，代码中通常写 else { right--; } 涵盖两板等高的情况。

1.5 为什么贪心移动短板而不是随机移动？

随机移动（如总是移动 left）也能找到所有可能的组合吗？不能。如果总是 left++，当最优解的左端点在数组右半段时，算法永远不会考察到它。

对撞指针的本质是：保证最优解一定在”未来搜索范围”内。每次移动短板，都能严格缩小搜索范围（排除以当前端点为端的所有组合），同时保证最优解未被排除。

---

第 2 章 LeetCode 42：接雨水

2.1 题目

LeetCode 42 - Trapping Rain Water（困难）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

输入：height = [4,2,0,3,2,5]
输出：9

2.2 核心观察：每个位置能接多少水？

接雨水和盛水容器不同：盛水容器是找”最优的两条线”，接雨水是计算”每个位置实际能接的水量之和”。

对于位置 i，它能接的水量是多少？

$\text{water}[i]=\max (0,\min (\text{leftMax}[i],\text{rightMax}[i])-\text{height}[i])$

其中：

• leftMax[i]：位置 i 左侧（含 i）的最大柱子高度
• rightMax[i]：位置 i 右侧（含 i）的最大柱子高度
• $\min (\text{leftMax}[i],\text{rightMax}[i])$：两侧最高柱子中的矮者（短板）决定了水位
• 减去 height[i]：柱子本身不存水

直觉：每个位置上方的水，由左右两侧最高柱子中的短者决定水位，再减去柱子自身高度。

2.3 解法一：前后缀预处理（最直观）

两次扫描分别计算 leftMax 和 rightMax 数组，然后一次扫描计算总水量。

public int trap(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
 
    // 计算每个位置左侧的最大高度（含本身）
    int[] leftMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
 
    // 计算每个位置右侧的最大高度（含本身）
    int[] rightMax = new int[n];
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }
 
    // 计算每个位置的水量
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return total;
}

时间复杂度：$O(n)$；空间复杂度：$O(n)$（两个额外数组）。

2.4 解法二：对撞指针（$O(1)$ 空间）

对撞指针解法是前后缀预处理解法的空间优化版本，空间从 $O(n)$ 降到 $O(1)$。

关键洞察：计算位置 i 的水量时，只需要 $\min (\text{leftMax}[i],\text{rightMax}[i])$。如果已经知道”哪边的最大值更小”，就能直接计算当前位置的水量，不需要预先算出整个 leftMax 和 rightMax 数组。

具体来说：

• 维护 leftMax（到目前为止 left 左侧的最大高度）和 rightMax（到目前为止 right 右侧的最大高度）
• 如果 leftMax < rightMax：位置 left 的水量为 leftMax - height[left]（因为右边至少有一个高度 ≥ rightMax > leftMax 的柱子，短板一定是左侧，水量由 leftMax 决定），left++
• 否则：位置 right 的水量由 rightMax 决定，right--

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int total = 0;
 
    while (left < right) {
        // 更新左右两侧已知的最大高度
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
 
        if (leftMax < rightMax) {
            // 左侧短板已确定（leftMax），可以计算 left 位置的水量
            total += leftMax - height[left];
            left++;
        } else {
            // 右侧短板已确定（rightMax），可以计算 right 位置的水量
            total += rightMax - height[right];
            right--;
        }
    }
    return total;
}

时间复杂度：$O(n)$；空间复杂度：$O(1)$。

2.5 对撞指针解法的正确性：与前后缀解法的等价性

为什么这个解法是正确的？看起来 leftMax 和 rightMax 都是”局部”的（只到当前指针位置），而不是”全局”的（整个数组的前/后缀最大值），为什么能得到正确结果？

命题：当 leftMax < rightMax 时，leftMax == leftMax_全局[left]（即当前 leftMax 等于预处理数组中 left 位置的全局前缀最大值），因此计算出的水量是正确的。

证明：

对于任意 left 位置，全局 leftMax_全局[left] = max(height[0], height[1], ..., height[left])。对撞指针中的 leftMax 是从 0 到当前 left 的最大值，正好就是 leftMax_全局[left]（因为 left 只向右移动，每次移动前更新 leftMax = max(leftMax, height[left])）。

但是，rightMax 在对撞指针中只是”从 n-1 到当前 right 的最大值”，而 rightMax_全局[left] = max(height[left], ..., height[n-1])，前者小于等于后者。

当 leftMax < rightMax 时：

$\text{leftMax}<\text{rightMax}\le \text{rightMax\_全局}[left]$

因此 $\min (\text{leftMax\_全局}[left],\text{rightMax\_全局}[left])=\text{leftMax\_全局}[left]=\text{leftMax}$。

位置 left 的水量 = $\text{leftMax}-\text{height}[left]$，正确。$\square$

核心概念：利用局部信息推导全局结论

对撞指针解法的精妙之处在于：leftMax < rightMax 这个条件保证了”即使 rightMax 不是真正的全局右侧最大值，但它至少大于 leftMax，所以全局右侧最大值也大于 leftMax，短板一定在左侧”。局部信息 rightMax 作为全局右侧最大值的下界，已经足够判断短板位置。

2.6 三种解法对比

解法	时间复杂度	空间复杂度	代码复杂度	适用场景
前后缀预处理	$O(n)$	$O(n)$	低	代码清晰，理解成本低
对撞指针	$O(n)$	$O(1)$	中	追求空间最优
单调栈	$O(n)$	$O(n)$	高	能逐行计算水量，适合流式数据

面试中推荐先写前后缀预处理（思路清晰易讲解），再说”可以用对撞指针优化到 $O(1)$ 空间”，展示深度。

---

第 3 章 两道题的对比：相同框架，不同难点

3.1 相同的框架

两道题都使用对撞指针，框架几乎一模一样：

while (left < right):
    计算当前状态
    根据某个条件决定移动哪个指针
    更新答案

不同点在于”移动指针的条件”和”其正确性的论证”：

	Container With Most Water	Trapping Rain Water
移动条件	移动短板（height[left] < height[right]）	移动 leftMax 较小的一侧
计算水量方式	两板之间一次性计算	每个位置分别计算
正确性关键	短板决定水量上界，其他组合均不更优	leftMax < rightMax 保证左侧是全局短板

3.2 常见的混淆

Container With Most Water 的常见错误：用单调栈解法（单调栈适合 Trapping Rain Water 的”逐行”计算，不适合”找最大值”问题）。

Trapping Rain Water 的常见错误：把对撞指针的移动条件与 Container With Most Water 混淆——接雨水移动的是 leftMax < rightMax（两侧预知最大值的比较），而不是 height[left] < height[right]（当前两端高度的比较）。

---

第 4 章 边界条件与特殊情况

4.1 Container With Most Water 的边界

height 全相同：如 [3, 3, 3, 3]。每步 else { right--; }，从右端开始收缩，直到 left = 0, right = 1，检查 3 * 1 = 3，答案为初始 3 * (n-1) = 9。

只有两条线：left=0, right=1，计算一次后 left < right 不成立，退出循环，返回正确结果。

4.2 Trapping Rain Water 的边界

空数组或单元素：left >= right，循环不进入，返回 0。正确（一根或零根柱子无法接水）。

全相同高度：如 [3, 3, 3, 3]，每个位置 leftMax == rightMax == height[i] == 3，total += 0，返回 0。正确（没有低洼，无法积水）。

单调递增/递减：如 [1, 2, 3, 4, 5]，无论从哪端出发，始终满足”一侧更高”，水量为 0。正确。

---

小结

本文深入分析了对撞指针在几何问题中的两个最重要应用：

• Container With Most Water：移动短板，每步排除以当前端点为端、宽度更小的所有组合。证明关键：短板决定水量上界，移动后不可能错过更优解。
• Trapping Rain Water：维护 leftMax 和 rightMax，利用”局部 rightMax 作为全局右侧最大值的下界”判断短板位置，实现 $O(1)$ 空间的对撞指针解法。

两道题共同揭示了对撞指针算法正确性证明的核心方法：证明每次移动不会排除包含最优解的组合。下一篇开始进入快慢指针的世界，从链表环检测和 Floyd 判圈算法入手，分析快慢指针的数学本质。