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从i1到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^5O(n²) 意味着最多要执行接近 5×10^9 次运算直接超时。暴力解法的价值不在“能不能过”而在于它暴露了问题的数学结构。你写出双层循环后盯着这个公式看一会儿就会意识到两件事第一面积被较小的那根柱子死死压住第二两个端点越往外围宽度贡献越大。这两个观察是引出双指针的全部依据。2.2 短板效应容器的高度由矮的说了算用生活中的例子类比一个木桶能装多少水取决于最短的那块木板。这道题就是木桶效应的二维版两根柱子的高度一个高一个矮水位只会涨到矮柱子的高度高的那部分完全是摆设。这个直觉对解题有什么用它告诉我们当左右指针指向某两根柱子时阻碍面积继续变大的是较矮的那一根。如果此时你想要通过移动指针来寻找更大的面积正确方向只有一个——把较矮的那一侧指针往中间移动换一根更高的柱子来试试。移动较高的一端没有任何收益因为高度已经被矮柱锁死了而宽度还会变小面积必然缩小。听起来像贪心对不对但它不是无脑贪心后面需要用数学证明这个策略不会漏掉最优解。实际面试里很多人卡住的不是写代码而是这个“为什么安全”的证明。给面试官讲一个够用的方法至少要有当前状态、排除逻辑、候选集收缩三个层次的表述下面我一步步展开。3. 双指针为什么正确核心论证与反例3.1 指针移动策略的完整描述双指针解法的流程是这样的初始时left 0right 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作为左边界的任意其他容器设右边界为kl 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 0right 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题目描述同样是柱子、同样用双指针很容易搞混。但它们的计算目标完全不一样。盛水最多容器问的是“选两根柱子能框住的最大水量”本质是最大化一个矩形的面积。接雨水问的是“下完雨后所有柱子之间的凹槽总共能存多少水”它要考虑每一根柱子左右两侧的最大高度把整片地形上的积水逐列累加。对比一下维度盛水最多的容器接雨水目标找两根柱子使矩形容量最大所有凹槽积水的总量状态变量左右两个端点左右遍历时的峰值高度核心公式min(h[l],h[r]) * (r-l)min(leftMax, rightMax) - h[i]经典解法双指针向内收缩双指针、单调栈或两次遍历时间复杂度O(n)O(n)面试时如果两道题一起被问到主动说出这个对比会让面试官觉得你具备体系化的总结能力而不只是在背题目。5.2 常见变体最相近的双指针题目把“盛水最多的容器”换一层皮就是两数之和一类的双指针问题。比如 LeetCode 第 167 题“两数之和 II - 输入有序数组”在有序数组里用左右指针根据和的大小调整方向再比如“三数之和”排序后固定一个数剩下两个数用双指针收尾。它们的共同框架是有序或可排序的数据结构上利用单调性移动指针避免重复枚举。还有一种变体是把一维扩展到二维在二维矩阵里找两个点使矩形区域盛水最多。这个问题复杂度会陡增不再是简单的双指针能解的需要结合矩阵前缀和、二分等技巧。面试中常见做法是先让对方写出一维双指针解法再问“如果变成二维你怎么想”这其实是在考察你有没有养成把基础模型抽象出来的习惯。5.3 双指针的通用套路什么情况下该想到它结合实战经验双指针适用于这几种信号数组是有序的或可以排序的问题要求找两个元素之间的关系暴力解是 O(n²) 且有单调性可以利用。单调性是关键因为它支持“当前状态不好就跳过一部分状态”的决定。盛水容器恰好具备这种单调性移动矮指针对应的面积被当前面积压住所以这一侧不需要再扫。如果用一句话总结这类题的解题心法就是“试图找到能证明一部分答案可以被抛弃的条件”。双指针不是靠魔法而是靠合理地剪掉不可能成为最优解的状态组合。6. 面试实战怎么讲这道题才能拿加分6.1 建议的叙述路径从暴力到证明再到代码如果面试官让你现场做这道题不要上来就写双指针。正确的流程是先说清楚思路演变因为对方想看你的过程而不只是结果。我推荐的表述顺序是这样的。第一句“这道题最直接的做法是双重循环枚举所有柱子对O(n²)。”第二句“我注意到面积受到短板的限制如果两根柱子一高一矮面积只取决于矮的那根。”第三句“那我从最宽的位置开始用两个指针指向数组两头每次把较矮的那一侧指针往中间移因为以它为边界的组合已经被当前面积压得死死的排除是安全的。”第四句“这样左右指针总共移动 n 次时间复杂度 O(n)空间 O(1)。”最后再写代码。这套话术之所以好用是因为它把“为什么这么做”和“为什么正确”都放进了叙述里。面试官听到第三句就会知道你是真的理解双指针而不是背了答案。6.2 常见错误的速查清单错误表现原因分析纠正方式移动较高的指针导致漏解没有理解短板决定容器高度只有矮柱才限制面积高柱移动后宽度变小没有收益while 条件写成left right边界意识不清左右相等时宽度为 0循环无意义漏掉数组长度小于 2 的判断未考虑边界输入生产环境先判空和长度再进入双指针逻辑用height[left] height[right]作为移动条件方向写反写完之后用反例[1,2,4,3]手动走一遍面积变量用 int 但范围可能更大数据规模考量不足说明 LeetCode 范围内 int 足够大规模用 long代码写完手测一两个用例是加分动作。我自己习惯在纸上用[1,8,6,2,5,4,8,3,7]走一遍这个用例答案是 49也是平台的标准示例。手动追踪几轮比干巴巴地说“我提交过了”更有说服力。6.3 追问阶段怎么答面试官通常会追加几个问题。第一个是“如果两根柱子高度相等移动哪边”你可以回答都可以并说明原因因为相等时排除左边还是右边都不会漏掉更优解。第二个问题是“能不能优化到比 O(n) 更快”理论上任何算法都要看每根柱子的高度输入就要 O(n)所以不可能有亚线性的解法。你要明确说“最优解下界至少是 O(n)”这个回答能展示复杂度下界的意识。第三个问题是“这个思路能用到哪些题上”你可以顺带提两数之和、三数之和、接雨水。如果面试官心情好还可以补充一句“本质是状态空间剪枝每一步排除一个不可能变为最优的集合”这句话容易留下记忆点。最后再分享一点刷题心得这道题我前后刷过不下三遍每一遍都有新体会。第一遍是看题解抄代码能过但不理解第二遍是闭关推导证明写到纸上才发现“为什么矮柱安全”这个结论需要反证法而不是眼睛一看就能接受第三遍是给同事讲解讲着讲着发现自己的表述越来越顺也慢慢能把它和矩阵单调栈、接雨水这类题挂上钩。如果你也是刚开始刷算法题我的建议是不要贪多。一道题刷完之后花 20 分钟把三个东西写出来核心思路一句话、正确性证明一段话、变体题两个名字。这三个东西积累多了面试时候的自然流露完全不是死记硬背的效果。盛水容器只是双指针的一张入场券但吃透它的过程比做完十道简单题更值钱。