LeetCode 11盛水最多的容器：双指针算法证明与代码实现

刷 LeetCode 11 盛水最多的容器之前，我一直觉得双指针是个玄学：两个指针一左一右往中间走，凭什么移动短的那一边就一定不会错过最优解？直到我把这道题真正想明白，才发现双指针背后是一套非常干净的“候选淘汰”逻辑，根本不是靠感觉猜的。

先给没做过这道题的朋友说清楚题目：给定一个非负整数数组 height，数组下标是柱子的位置，值代表柱子高度。现在挑两根柱子当容器的左右壁，两根柱子之间的水平距离是容器宽度，水位由较矮那根柱子决定，求能盛水的最大面积。这道题在 LeetCode 上是第 11 题，属于双指针入门必刷，也是后续接雨水、三数之和等题目的逻辑起点。

这篇文章我打算按自己从“暴力解超时”到“双指针一遍过”再到“面试时能讲清证明”的复习路径来写：先拆题意，再写暴力解，然后推导双指针正确性，最后给代码、讲变体。无论你是刚开始刷题的萌新，还是想补证明的进阶选手，都值得花十分钟读完。

1. 先把题意拆开：盛水面积到底怎么算

1.1 一个容易画错的水桶

“容器”“盛水”这两个词很容易让人脑补出一个能斜着放的水桶，但这道题里的容器就是一个放在平面上的水槽：左右两根柱子竖在 x 轴上，中间区域是底，水只能在两根柱子之间存。水面始终是水平的，所以实际水深由较短的那根柱子决定，水再多也会从矮的一侧溢出去。

用公式写就是一行：

area = (j - i) × min(height[i], height[j])

这一行里有两个地方特别容易出问题。第一，宽度必须是下标差 j - i，不是 j - i + 1，因为柱子的位置是端点，不是格子，中间隔了多少个下标，宽度就是多少。第二，高度必须取 min，不是 max，也不是平均数。我见过不少人嘴上说着“矮的求 min 高的求 max”，一写代码就顺手敲成 max，问他就是手滑。

这里我建议你直接把公式背下来：面积 = 水平距离 × 短板高度。面试时能脱口说出这个公式，等于告诉面试官你已经理解了物理场景，而不是在背题。

1.2 正式定义与边界情况

用数学语言规范一下：给定数组 height，长度 n，要求找出所有 i < j 中 (j - i) × min(height[i], height[j]) 的最大值。题目给定的 n 最大到 10^5 量级，height[i] 是非负整数，可以等于 0。

边界情况我建议刷题时养成习惯，提交前先过一遍：

• n < 2：没有两根柱子可选，答案直接是 0。
• 数组全是 0：任意两根柱子的面积都是 0。
• 所有柱子等高的极端场景：答案就是最远两根柱子的距离乘以这个高度，因为宽度越大越好。

这些边界单独拎出来没什么难度，但很多人提交超时或者答案错误，往往就是暴力解忘了处理空数组，或者双指针循环条件写错，导致单元素数组直接越界。

1.3 拿经典用例手算一遍

以原题经典用例 height = [1, 8, 6, 2, 5, 4, 8, 3, 7] 为例。如果挑下标 1 和下标 8 这两根柱子，高度分别为 8 和 7，水平距离是 8 - 1 = 7，面积就是 7 × min(8, 7) = 49。

这个 49 恰好是这道题的最优答案，但它是遍历完所有组合之后才确定的，不是一眼看出来的。我建议你把这个数组抄下来，自己动手算几组组合，比如 (0, 8) 面积是 8 × 1 = 8，(0, 7) 是 7 × 1 = 7，(1, 6) 是 5 × 8 = 40，能直观感受到“宽和高互相制约”的微妙关系。这比直接看题解有用得多。

2. 暴力解法：三分钟写完，然后被数据教你做人

2.1 双层循环的实现

拿到这道题，绝大多数人的第一反应就是暴力枚举所有两根柱子的组合。代码非常直白：

def max_area_bruteforce(height): n = len(height) ans = 0 for i in range(n): for j in range(i + 1, n): area = (j - i) * min(height[i], height[j]) ans = max(ans, area) return ans

两层循环，内层从 i + 1 开始，避免重复计算同一对柱子。每一对都算一次面积，更新最大值。逻辑上没有任何问题，跑小样本也完全正确。

我第一次刷这道题就是先写的暴力解，当时 endpoint 测试数据很友好，直接过了，我还以为这题就这么简单。直到我把数组长度拉到 10^5 再测，那叫一个酸爽，跑了几分钟都没出结果，最后强制终止。

2.2 复杂度的账要算清楚

暴力解的时间复杂度是 O(n²)，具体操作次数大约是 n(n-1)/2。当 n = 10^5 时，这是 5 × 10^9 次乘法运算和大小比较，任何常规语言在 1 到 2 秒的限制下都跑不完。Python 更夸张，这种量级的纯循环可能要跑几十秒到几分钟。

空间复杂度是 O(1)，只用了常数个变量，这一点倒是很好。但时间上扛不住，所以它只能作为教学演示和验证基准，不能作为正式解法出场。

2.3 暴力解在面试里的定位

面试时如果你先写暴力解再优化，其实是加分行为，因为它展示了你的思考过程：先保证正确，再考虑效率。但要注意，写完暴力解之后一定要主动指出“这个解法在 n 较大时不可行，因为 O(n²) 的复杂度无法承受”，然后自然地过渡到双指针。

这里分享一个我的个人习惯：写完双指针解法之后，不要直接提交，而是先写一个暴力解当“对拍器”，用随机生成的小数组把两个解法跑一遍，逐个对比结果。这道题虽然简单，但“相等高度时该移哪个指针”这种细节，你对拍几次就能彻底放心。

3. 双指针为什么是对的：直觉、反例与严谨证明

3.1 从最宽的地方开始收缩

双指针的第一步是让左指针指向下标 0，右指针指向下标 n - 1，也就是一开始就选中距离最远的两根柱子，宽度最大。接下来每走一步，宽度减一，我们要决定丢掉哪一端。

这个问题的本质变成：每一步该移动左指针还是右指针？如果把两根指针都试一遍，那又回到暴力枚举了。双指针的精髓在于，每一步能确定性地淘汰掉其中一端，而且被淘汰的那一端再也不可能出现在更优解里。

3.2 短板效应：移长的那根一定没希望

假设当前左指针的高度是 h[i]，右指针的高度是 h[j]，并且 h[i] < h[j]。当前面积是 (j - i) × h[i]。现在考虑要不要移右指针 j。如果你把右指针往左移一位，宽度变成 j - i - 1，必然变小；而新的右柱子高度如果是 h[j']，那么 min(h[i], h[j']) 最多不会超过 h[i]。

换句话说，无论右指针移到哪根更高的柱子上，水面高度仍然被左侧那根矮柱子卡死，宽度却一直在縮小，所以面积只会更小，不可能超过当前值。右指针这条分支完全没戏。

3.3 候选淘汰的严谨说法

面试时光说“短板效应”其实不够严谨，更准确的表达是“候选淘汰”。当 h[i] ≤ h[j] 时，对于固定的左端点 i，任意右端点 k 只要满足 i < k < j，面积都是 (k - i) × min(h[i], h[k])。

这里 min(h[i], h[k]) 永远 ≤ h[i]，而 k - i 永远 < j - i，所以这个面积严格小于当前面积 (j - i) × h[i]。结论是：左端点 i 和当前右端点 j 之间所有可能的配对，最优的那个就是我们刚刚算过的当前组合。既然 i 已经不可能和其他任何端点组合出更大的面积，i 这个候选就可以永久淘汰，直接左移。

当我习惯用淘汰视角去理解时，双指针就再也不是玄学了。它每走一步都在做一次“剪枝”，把一个不可能产生最优解的候选端点从集合里删掉，一共 n 个端点，删 n 次，复杂度自然就是 O(n)。

3.4 双指针的演算过程

还是用经典数组 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，把完整的指针移动过程列出来：

遍历完 8 步，最大值停留在第 2 步的 49，这就是答案。把这张表在自己纸上画一遍，指针移动和面积变化的规律就一目了然了。

4. 代码实现：标准双指针与三个易错点

4.1 Python 标准版

def max_area(height): left, right = 0, len(height) - 1 ans = 0 while left < right: area = (right - left) * min(height[left], height[right]) ans = max(ans, area) if height[left] < height[right]: left += 1 else: right -= 1 return ans

这个版本是面试和日常刷题的基准写法。每次循环先算当前候选的面积，然后移动“更矮那一边”的指针。如果两边高度相等，代码会把右指针向左移动，这也完全正确，背后的原因我在下一节专门展开。

4.2 Java 标准版

class Solution { public int maxArea(int[] height) { int left = 0; int right = height.length - 1; int ans = 0; while (left < right) { int area = (right - left) * Math.min(height[left], height[right]); ans = Math.max(ans, area); if (height[left] < height[right]) { left++; } else { right--; } } return ans; } }

Java 版和 Python 版思路完全一致，只是语法不同。核心循环的退出条件是 left < right，当两个指针相遇时，宽度为 0，没有继续计算的必要。

4.3 进阶优化：跳过不可能更高的柱子

标准双指针已经是 O(n) 了，但还有一个可以锦上添花的优化思路：每轮算完当前面积后，不要只是移动一格，而是把“不可能超过当前高度”的柱子一次性跳过。

def max_area_skip(height): left, right = 0, len(height) - 1 ans = 0 while left < right: h = min(height[left], height[right]) ans = max(ans, (right - left) * h) while left < right and height[left] <= h: left += 1 while left < right and height[right] <= h: right -= 1 return ans

这段代码的正确性其实值得想一下。假设当前短板高度是 h，左指针如果移到一根高度 ≤ h 的新柱子上，新面积的高度部分最多还是 h，而宽度反而更小，所以必然不可能超过刚才算的面积。同理，右指针也可以跳过所有 ≤ h 的柱子。这样每一轮多跳几步，虽然最坏情况仍然是 O(n)，但很多场景下能减少循环次数。

我个人的建议是：面试中先写标准双指针，等面试官追问“还能不能优化”时再给出跳过版本，并当场把正确性讲清楚。如果你一上来就写跳过版，又解释不清楚为什么不会漏解，反而容易减分。

4.4 提交时最容易翻车的三个细节

第一个坑：宽度写成 j - i + 1。这通常是把数组当格子数而不是当坐标点来理解导致的，结果比正确答案大一圈，而且测试数据越大错得越离谱。

第二个坑：取高度时写成了 max。这个错误很隐蔽，因为视觉上长得越高越能盛水，但实际上水会从矮的那边流走，必须用 min。建议提交前用几个高度差异大的用例手动验证一下。

第三个坑：循环条件写成 left <= right。当 left 和 right 相等时，两根指针指向同一根柱子，宽度是 0，面积也是 0，虽然不会出错，但之后指针交叉再访问数组就越界了。这道题老老实实用 while left < right 就好。

把三个坑和复杂度汇总成一张表：

5. 面试官把这些变体抛过来时怎么接

5.1 相等高度：移左还是移右？能不能一起移？

当 height[left] == height[right] 时，标准代码走的是 else 分支，也就是右指针左移。那么问题来了：这个时候移左指针行不行？

答案是行。因为两根柱子高度相等，按淘汰逻辑，左指针和当前右指针之间的所有配对已经不可能超过当前面积，右指针同理。所以左移、右移甚至两边同时移都是正确的。我面试写代码时倾向于只移右指针，因为这样逻辑最简单，也最容易向面试官解释；如果面试官追问，再展开说明“其实两边的候选都可以安全淘汰”。

这里有个容易翻车的地方：如果你选择两边同时移，一定要在代码里写成两个 if，而不是 if-else，否则实际上只移了一边。我见过有人讲得头头是道，一写代码就写成了 else，结果逻辑和自己说的完全对不上。

5.2 从盛水容器到接雨水：双指针的两副面孔

很多人刷完这道题，紧接着会碰到另一道经典题：接雨水，LeetCode 第 42 题。两道题共享“短板”直觉，但思路有本质区别。盛水容器是找一对柱子使面积最大，只需要看当前两端的高度，取较小值乘以宽度即可；接雨水则是统计所有凹槽里的积水量，需要同时维护左侧最大高度边界和右侧最大高度边界，再逐个位置累加。

我面试时经常被连着问这两道题，如果你能主动答出它们的区别——一个是“取端点、找最优对”，一个是“维护边界、逐格累加”——面试官会认为你是真的理解双指针，而不是背模板。

5.3 什么时候该想到双指针：三个适用信号

根据我做题的经验，一道题适合用双指针通常有三个信号。第一，问题可以转化为两个端点的收缩过程，每一步只需要决定丢弃哪一端。第二，存在某种单调性或短板限制，使得被丢弃的那一端在数学上不可能再参与更优解，也就是候选淘汰可以严格证明。第三，整个过程只需要常数级别的额外空间，不需要哈希表或前缀和辅助。

典型例子包括两数之和 II、三数之和、盛水容器、接雨水。刷到这些题时，先对照这三个信号想想，比直接套模板要靠谱得多。

6. 最后说点刷题体会：别急着背代码

我第一次做这道题时，暴力解过了小数据就开始飘，一提交就超时，然后老老实实打开题解背双指针写法。背完能写出来，但面试官一问“为什么移动矮的指针”，我就只能说出“因为矮的决定了高度”，再往深一层就卡住了。

后来我花了一个晚上，把双指针的淘汰过程在草稿纸上画了几十遍，又用随机数组对拍了暴力解和双指针解，才真正把这道题吃透。从那以后，接雨水、三数之和这类双指针题我上手快了很多，因为底层那套“候选淘汰”的思维已经通了。

如果你现在正被这道题折磨，我的建议是：不要只看题解，先自己画一遍指针移动表，再试着用“对于固定左端点，任何右端点都不可能更好”的句式把证明写出来，最后用三个边界用例做自测。把这一套走完，你收获的不只是这一道题的解法，而是一种能迁移到很多题目上的思考方式。顺便说一句，你还可以在纸上模拟跳过版本的指针轨迹，验证一下优化前后答案始终一致，这个过程本身就很解压。