LeetCode 11题盛水最多容器：双指针算法详解与面试攻略

1. 先读懂题目：这道题到底在问什么

如果你准备 Java 开发岗面试，LeetCode 第 11 题“盛水最多的容器”几乎是绕不开的一道题。它看起来简单，但真正能一次讲清楚的人不多。题目原文是给一个非负整数数组height，每个元素代表坐标(i, height[i])处竖着一根柱子，我们需要从中挑出两根柱子，和 x 轴围成一个容器，计算它能装多少水，然后找出最大容量。

容器装水的多少只取决于两个因素：两根柱子之间的距离，以及较短那根柱子的高度。换句话说，容器容量 = 两端柱子的最小高度 × 横向距离。用公式写就是S(i, j) = min(height[i], height[j]) * (j - i)。

这道题考察的是典型的双指针思想：同时在数组的两端各放一个指针，根据某种策略往中间收缩，在线性时间内完成扫描。很多文章会直接甩出代码，但如果你不明白“为什么移动较矮的那一端”这个核心逻辑，面试时一深问就会露馅。这篇文章我就把这个算法的证明、代码实现、面试表述和周边变体一次性讲透。

适合谁看？刚开始刷题、准备暑期实习面试的在校学生，工作一到三年想补一补算法短板的后端开发，以及想给同事讲明白双指针原理的工程师。确保你看完后，不仅能手写这道题，还能用自己的话把“为什么对”讲给面试官听。

2. 暴力解法能做什么，又漏掉了什么

2.1 先写能跑的东西：双重循环穷举

拿到这道题，第一反应肯定是枚举所有柱子对，也就是用两层循环遍历数组。外层指针i从 0 到n-1，内层指针j从i+1到n-1，每对组合都算一次面积，用一个变量维护最大值。

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

这段代码简单可靠，任何科学计算器都能验证它的正确性。问题是规模一大就扛不住。假设数组长度是 n，比较次数是 n(n-1)/2，时间复杂度是 O(n²)。LeetCode 上给的测试用例规模到 10^5，O(n²) 意味着最多要执行接近 5×10^9 次运算，直接超时。

暴力解法的价值不在“能不能过”，而在于它暴露了问题的数学结构。你写出双层循环后，盯着这个公式看一会儿，就会意识到两件事：第一，面积被较小的那根柱子死死压住；第二，两个端点越往外围，宽度贡献越大。这两个观察是引出双指针的全部依据。

2.2 短板效应：容器的高度由矮的说了算

用生活中的例子类比，一个木桶能装多少水取决于最短的那块木板。这道题就是木桶效应的二维版：两根柱子的高度一个高一个矮，水位只会涨到矮柱子的高度，高的那部分完全是摆设。

这个直觉对解题有什么用？它告诉我们，当左右指针指向某两根柱子时，阻碍面积继续变大的，是较矮的那一根。如果此时你想要通过移动指针来寻找更大的面积，正确方向只有一个——把较矮的那一侧指针往中间移动，换一根更高的柱子来试试。移动较高的一端没有任何收益，因为高度已经被矮柱锁死了，而宽度还会变小，面积必然缩小。

听起来像贪心对不对？但它不是无脑贪心，后面需要用数学证明这个策略不会漏掉最优解。实际面试里，很多人卡住的不是写代码，而是这个“为什么安全”的证明。给面试官讲一个够用的方法，至少要有：当前状态、排除逻辑、候选集收缩三个层次的表述，下面我一步步展开。

3. 双指针为什么正确：核心论证与反例

3.1 指针移动策略的完整描述

双指针解法的流程是这样的：初始时left = 0，right = height.length - 1，两个指针分别指向数组最左和最右的柱子。计算当前面积，更新最大值。然后比较两根柱子的高度，谁矮就移动谁：如果height[left] < height[right]，就left++；否则right--。这样一直缩圈，直到两个指针相遇。

这段流程背后隐藏着一个状态空间剪枝的思想，每次移动都相当于排除了“当前较矮柱子作为容器边界的所有可能组合”，这个排除操作是整道题的灵魂。只要你能证明被排除的组合里不可能出现全局最优解，那这个算法就正确。

3.2 正确性证明：排除矮柱是安全的

假设当前指针位置是l和r，满足l < r，当前面积为S(l, r) = min(height[l], height[r]) * (r - l)。

分两种情况讨论。

第一种，height[l] < height[r]，矮柱子在左边。此时以l作为左边界的任意其他容器，设右边界为k（l < k < r），它的面积是min(height[l], height[k]) * (k - l)。由于min(height[l], height[k]) <= height[l]，并且k - l < r - l，所以这个面积严格小于height[l] * (r - l)，也就是小于当前的S(l, r)。

这说明什么？以当前矮柱l为边界、另一条边落在(l, r]范围内的所有组合，没有一个能超过当前已经计算出的面积。那这些组合还有必要留到后面再算一遍吗？没有必要。因为它们的最优上限已经低于当前值，更不可能超过全局最大值。于是把l这根柱子排除掉，指针右移，是绝对安全的。

第二种情况对称，height[r] < height[l]，矮柱子在右边，同样可以证明，以r为右边界的任意容器面积都不会超过当前面积，所以r可以被安全排除，指针左移。

这个证明的逻辑链是“我排除的不是一个解，而是一个集合——所有以它为边界的组合”。每走一步，候选组合的规模都缩小一大块，但同时保证最优解仍在剩余集合中。当两个指针相遇时，所有可能的柱子对都被覆盖或排除过一遍，最大值自然就找到了。

3.3 为什么要举反例：移动高柱子会漏解

很多初学者会想：既然矮柱是短板，那把高的移开，换一根更高的来拉高度不行吗？我们用一个反例亲手走一遍，比背十遍结论都管用。

数组[1, 2, 4, 3]，初始left = 0，right = 3，面积 =min(1, 3) * 3 = 3。此时height[0] = 1 < height[3] = 3，正确的做法是移动左指针到1，得到(1, 3)，面积 =min(2, 3) * 2 = 4，这就是全局最优解。

如果错误地移动右指针，状态变成(0, 2)，面积 =min(1, 4) * 2 = 2。接下来无论怎么走，都没法再碰到4这个答案。你以为是移动一根柱子的小事，实际是漏掉了最优解组合(1, 3)。所以规则不是“随便移哪边都行”，而是必须固定移动较矮的一侧。

同理，当height[l] == height[r]时，两边高度相等，移动哪边都是安全的。因为左边柱子的所有组合面积被当前面积覆盖，右边柱子的所有组合同样被覆盖，二者互不影响，所以你选择left++还是right--都可以，最终答案不变。有些实现里用else分支统一移动右边，也没有问题。

4. Java 代码落地：一个 while 循环搞定

4.1 标准实现与逐行解读

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

这个版本已经足够应付所有正常面试场景。代码里最容易被忽略的是while (left < right)这个条件，它保证两个指针在相遇前至少还有一格距离，因为当left == right时，两根柱子重合，宽度为 0，装不了任何水。如果你写成left <= right，就会出现一次多余的无效计算，虽然不影响结果，但面试官容易觉得你边界意识模糊。

每次循环里我们用Math.min取短板高度，用right - left算宽度，乘起来就是当前容器面积，然后和max比较。更新完面积后再判断移动方向。这样写的好处是逻辑顺序和人脑的思考顺序一致：先算面积，再决定下一步往哪走。

4.2 边界条件与鲁棒性处理

面试官喜欢追问一些特殊输入。比如数组长度小于等于 1，此时根本找不到两根柱子，按道理应该返回 0。上面的代码在height.length为 0 时会抛出ArrayIndexOutOfBoundsException，所以生产环境里建议先加一个前置判断：

if (height == null || height.length < 2) { return 0; }

LeetCode 的题设默认数组长度至少为 2，所以平台提交时不加也能过，但你在面试手写代码时要主动提这一点，会显得经验老到。

还有数据溢出问题。题设中height[i]最大到 10^4，数组长度最大到 10^5，面积最大值约为 10^4 × 10^5 = 10^9，刚好卡在 int 的 2.1×10^9 以内，用 int 没问题。但如果面试官问“数据范围扩大 10 倍怎么办”，你要答得上来：把面积变量换成long，甚至用BigInteger，否则乘法结果会溢出变成负数，Math.max比较出一堆错误值。

4.3 复杂度指标：为什么是 O(n)

时间复杂度方面，left和right每轮循环必有且只有一个指针移动一步，两个指针从两端向中间靠拢，总共最多移动 n-1 次，所以时间复杂度是 O(n)，连排序预处理都不用，只扫描一遍数组。

空间复杂度是 O(1)，只用了left、right、h、water、max几个基本变量，没有额外数组，没有递归栈。这意味着即使数据规模上到百万级别，内存也毫无压力。对面试官来说，O(n) 时间 + O(1) 空间是这类题的标准答案形态，也是双指针算法最吸引人的地方。

4.4 一段可以口头补充的剪枝优化

还有一个优化点不用写在最终代码里，但说出来可以加分：宽度随着指针收缩不断减小，如果当前矮柱的高度乘以最大可能宽度都超不过已有最大值，就可以提前结束。思路是，每次循环前判断height[left] * (right - left) <= max且height[right] * (right - left) <= max，如果两边都满足就直接跳出循环。实际场景中这种剪枝对性能提升有限，而且增加代码复杂度。面试时你提一句“理论上可以在宽度缩小时做提前终止，但工程上收益不大”，就已经展示出对性能优化的敏感度了。

5. 一道题背后的一串题：与接雨水和变体题的对照

5.1 别混淆：盛水容器与接雨水是两道题

刷题刷多了会遇到另一道高频题“接雨水”（Trapping Rain Water），题目描述同样是柱子、同样用双指针，很容易搞混。但它们的计算目标完全不一样。

盛水最多容器问的是“选两根柱子，能框住的最大水量”，本质是最大化一个矩形的面积。接雨水问的是“下完雨后，所有柱子之间的凹槽总共能存多少水”，它要考虑每一根柱子左右两侧的最大高度，把整片地形上的积水逐列累加。

对比一下：

面试时如果两道题一起被问到，主动说出这个对比，会让面试官觉得你具备体系化的总结能力，而不只是在背题目。

5.2 常见变体：最相近的双指针题目

把“盛水最多的容器”换一层皮，就是两数之和一类的双指针问题。比如 LeetCode 第 167 题“两数之和 II - 输入有序数组”，在有序数组里用左右指针根据和的大小调整方向；再比如“三数之和”，排序后固定一个数，剩下两个数用双指针收尾。它们的共同框架是：有序或可排序的数据结构上，利用单调性移动指针，避免重复枚举。

还有一种变体是把一维扩展到二维：在二维矩阵里找两个点，使矩形区域盛水最多。这个问题复杂度会陡增，不再是简单的双指针能解的，需要结合矩阵前缀和、二分等技巧。面试中常见做法是先让对方写出一维双指针解法，再问“如果变成二维你怎么想”，这其实是在考察你有没有养成把基础模型抽象出来的习惯。

5.3 双指针的通用套路：什么情况下该想到它

结合实战经验，双指针适用于这几种信号：数组是有序的或可以排序的；问题要求找两个元素之间的关系；暴力解是 O(n²) 且有单调性可以利用。单调性是关键，因为它支持“当前状态不好就跳过一部分状态”的决定。

盛水容器恰好具备这种单调性：移动矮指针对应的面积被当前面积压住，所以这一侧不需要再扫。如果用一句话总结这类题的解题心法，就是“试图找到能证明一部分答案可以被抛弃的条件”。双指针不是靠魔法，而是靠合理地剪掉不可能成为最优解的状态组合。

6. 面试实战：怎么讲这道题才能拿加分

6.1 建议的叙述路径：从暴力到证明再到代码

如果面试官让你现场做这道题，不要上来就写双指针。正确的流程是先说清楚思路演变，因为对方想看你的过程，而不只是结果。我推荐的表述顺序是这样的。

第一句：“这道题最直接的做法是双重循环枚举所有柱子对，O(n²)。”第二句：“我注意到面积受到短板的限制，如果两根柱子一高一矮，面积只取决于矮的那根。”第三句：“那我从最宽的位置开始，用两个指针指向数组两头，每次把较矮的那一侧指针往中间移，因为以它为边界的组合已经被当前面积压得死死的，排除是安全的。”第四句：“这样左右指针总共移动 n 次，时间复杂度 O(n)，空间 O(1)。”最后再写代码。

这套话术之所以好用，是因为它把“为什么这么做”和“为什么正确”都放进了叙述里。面试官听到第三句就会知道你是真的理解双指针，而不是背了答案。

6.2 常见错误的速查清单

代码写完手测一两个用例是加分动作。我自己习惯在纸上用[1,8,6,2,5,4,8,3,7]走一遍，这个用例答案是 49，也是平台的标准示例。手动追踪几轮，比干巴巴地说“我提交过了”更有说服力。

6.3 追问阶段怎么答

面试官通常会追加几个问题。第一个是“如果两根柱子高度相等，移动哪边？”你可以回答：都可以，并说明原因，因为相等时排除左边还是右边都不会漏掉更优解。

第二个问题是“能不能优化到比 O(n) 更快？”理论上任何算法都要看每根柱子的高度，输入就要 O(n)，所以不可能有亚线性的解法。你要明确说“最优解下界至少是 O(n)”，这个回答能展示复杂度下界的意识。

第三个问题是“这个思路能用到哪些题上？”你可以顺带提两数之和、三数之和、接雨水。如果面试官心情好，还可以补充一句“本质是状态空间剪枝：每一步排除一个不可能变为最优的集合”，这句话容易留下记忆点。

最后再分享一点刷题心得

这道题我前后刷过不下三遍，每一遍都有新体会。第一遍是看题解抄代码，能过但不理解；第二遍是闭关推导证明，写到纸上才发现“为什么矮柱安全”这个结论需要反证法，而不是眼睛一看就能接受；第三遍是给同事讲解，讲着讲着发现自己的表述越来越顺，也慢慢能把它和矩阵单调栈、接雨水这类题挂上钩。

如果你也是刚开始刷算法题，我的建议是不要贪多。一道题刷完之后，花 20 分钟把三个东西写出来：核心思路一句话、正确性证明一段话、变体题两个名字。这三个东西积累多了，面试时候的自然流露完全不是死记硬背的效果。盛水容器只是双指针的一张入场券，但吃透它的过程，比做完十道简单题更值钱。