LeetCode第11题“盛水最多的容器”一道双指针入门必刷题也是面试里出现频率高得离谱的经典。很多人第一次看到这题脑子里第一反应就是暴力双重循环然后交上去发现超时接着就开始怀疑人生。其实这道题考查的并不是你会不会算面积而是你能不能从“暴力枚举所有组合”的思维惯性里跳出来找到那个让搜索空间从O(n^2)降到O(n)的关键结论。这篇文章我会从题目拆解讲起把双指针为什么正确、代码怎么写、边界怎么处理、变体怎么识别一次说透最后再聊聊我刷这题时踩过的坑以及怎么在面试里把这题讲出亮点。1. 盛水最多的容器题目到底在问什么1.1 原题快速还原与痛点定位题目要求很简单给你一个非负整数数组height每个元素代表一条垂直于x轴的线段起点在(i, 0)终点在(i, height[i])。要你找出两条线使得它们与x轴共同构成的容器能容纳最多的水返回最大面积。注意这个“容器”不是封闭的它只有左右两面墙没有顶底部是x轴。所以盛水量由三个因素共同决定左边墙的高度、右边墙的高度、两墙之间的水平距离。实际盛水高度取决于两堵墙中较矮的那一堵这就是经典的“短板效应”——一个木桶能装多少水取决于最短的那块木板。这道题在LeetCode上的编号是第11题排在第10题正则表达式匹配和第15题三数之和之间。别看它简单它和“接雨水”(LeetCode 42)、“最大矩形”(LeetCode 85)都是容器类问题的入门钥匙而且它考察的双指针思维在后续的题目里反复出现。我当时第一次刷这题的时候第一反应就是暴力枚举把所有(i, j)组合都算一遍但数组长度最大能有10^5O(n^2)的复杂度直接劝退。这也是这题的第一个痛点你第一时间能想到的解法往往不是题目想要的解法。1.2 暴力解法先走通再谈优化先别急着看双指针暴力解法再笨它也是你理解题意的第一步。暴力思路就是两层循环枚举所有左边界和右边界算面积取最大值。public int maxArea(int[] height) { int n height.length; int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { int area Math.min(height[i], height[j]) * (j - i); ans Math.max(ans, area); } } return ans; }这个代码没有逻辑错误但它的时间复杂度是O(n^2)。当n 10^5时内层循环要跑大约5 * 10^9次在大多数在线评测系统中都是稳稳的超时。面对这种“能算但算不动”的题你要养成的习惯不是直接去看题解而是先分析清楚暴力解法到底浪费了什么。在这个题里它浪费的部分在于绝大多数的组合根本不需要计算因为它们的面积不可能是最大值。那怎么判断哪些组合不可能是最大值这就引申出了双指针的核心逻辑。2. 双指针思路是怎么从0到1推出来的2.1 从“短板效应”出发缩小搜索空间这题的突破口在于思考“什么情况下面积一定不可能更大”。假设当前你有两个指针left和right分别指向数组的头和尾初始宽度最大面积为area min(height[left], height[right]) * (right - left)此时宽度是全局最大的水平距离。接下来为了寻找可能更大的面积你必须往中间移动其中一个指针宽度必然会变小。既然宽度变小了想让面积变大唯一的办法就是让高度变高。而高度由height[left]和height[right]中较小的那个决定。所以问题就变成了移动哪一个指针才可能让“容器高度”变高答案很直接哪个矮就移动哪个。因为如果你移动高的那个新的容器高度还是受限于矮的那一根高度不变或者变小宽度还在变小面积必然不可能超过当前值。但如果你移动矮的那一根新的那一侧可能更高这样容器高度就有机会变大。我用一个生活中的例子来类比你在两个不同身高的人之间拉一块布想让布与地面围成的“影子区域”变大最值得尝试的动作是换掉那个矮个子而不是费劲去垫高那个高个子——因为矮个子才是瓶颈。2.2 双指针为什么不会漏掉最优解关键证明很多初学者能理解“移动矮的更好”但无法理解“这样做一定能找到全局最优解”。这里必须把证明写透。设当前左右指针为left iright j且假设height[i] height[j]。当前面积为S height[i] * (j - i)。我们的策略是让i向右移动一步即抛弃(i, j)这个组合。为什么可以放心抛弃对于任意一个以i为左边界的组合(i, k)其中k满足i k j它的面积为S min(height[i], height[k]) * (k - i)由于k - i j - i宽度比当前小。对于高度如果height[k] height[i]那么min(height[i], height[k]) height[i]高度不变如果height[k] height[i]那么min(height[i], height[k]) height[i]高度变小或不变。无论哪种情况S height[i] * (j - i) S。也就是说所有以i为左边界的组合面积都不可能比当前(i, j)更大。那么左指针i对应的所有状态就都可以整体剪枝我们直接让i完全不会错过全局最优解。反过来说如果height[i] height[j]那么所有以j为右边界的组合都不可能比当前更大于是让j--。每次迭代都删除“边界中较矮的一侧”的全部可能性搜索空间不断收缩直到左右指针相遇。整个过程只需要O(n)次比较和计算。这个证明里最关键的一点就是“宽度减小 高度不再增加”这个双重约束。你要理解的是我们不是比较了两堵墙而是整批整批地淘汰了不可能成为答案的状态这才是双指针比暴力高效的本质。2.3 移动策略的细节什么时候移动哪个指针有了证明移动策略就很清楚了当height[left] height[right]时left当height[left] height[right]时right--。这里有个容易有争议的细节当两边相等时移动哪个从代码正确性来说移动哪边都不影响最终结果因为反正最大值已经记录了。但为了维持循环收敛性我一般习惯在相等时也移动右指针比如用if (height[left] height[right]) left; else right--;这种写法else会覆盖等于的情况。还有一个更激进的优化版本既然移动矮指针是为了找到更高的墙如果移动后新墙还是比原矮墙低那这个位置可以直接跳过。这就是“跳跃式双指针”或者“快速跳过更低墙”的优化方案。思路是在移动结束后加一层while判断如果新位置的高度不比原来的矮墙高就继续移动。while (left right) { int h Math.min(height[left], height[right]); ans Math.max(ans, h * (right - left)); if (height[left] height[right]) { // 跳过所有高度 height[left] 的位置 int cur height[left]; while (left right height[left] cur) { left; } } else { int cur height[right]; while (left right height[right] cur) { right--; } } }需要注意的是这种优化在极端数据下比如[1, 2, 3, 4, 5]能减少不少比较次数但它不会改变时间复杂度的大O阶。在面试场景中先写标准版再提一手这个优化点反而是加分项。3. 核心代码实现与多语言对照3.1 Java / Python / Go 三种实现直接抄先给出最标准的双指针解法。我平时刷题主要用Java和PythonGo是最近为了写服务端脚本才补上的三种语言其实写法几乎一致核心逻辑就那么几行。class Solution { public int maxArea(int[] height) { int ans 0; int left 0, right height.length - 1; while (left right) { int area Math.min(height[left], height[right]) * (right - left); ans Math.max(ans, area); if (height[left] height[right]) { left; } else { right--; } } return ans; } }Python版更简洁配合List[int]类型注解看起来非常舒服class Solution: def maxArea(self, height: List[int]) - int: left, right 0, len(height) - 1 ans 0 while left right: h min(height[left], height[right]) area h * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ansGo版需要注意的是没有内置的min函数Go 1.21之前要自己写一个或者用标准库。我在Go里面一般选择不引入额外依赖自己写一行判断func maxArea(height []int) int { left, right : 0, len(height)-1 ans : 0 for left right { h : height[left] if height[right] h { h height[right] } area : h * (right - left) if area ans { ans area } if height[left] height[right] { left } else { right-- } } return ans }3.2 复杂度分析与边界情况核对时间复杂度O(n)因为left和right总共移动n次每次只做常数时间的操作。空间复杂度O(1)只用了几个变量没有额外数组。边界情况是这种题最容易翻车的地方数组长度为2[1, 2]左右指针相邻只算一次面积1 * 1 1返回1。正确。所有高度相等[3, 3, 3]面积最大是3 * 2 6双指针对称收紧结果正确。高度递增[1, 2, 3, 4, 5]最左和最右组合1 * 4 4中间会有更大的组合吗2 * 3 6所以答案是6。数组长度为1或0题目约束一般n 2但为了健壮性可以加一个if (height.length 2) return 0;的防御性判断。我在刷题时会额外注意整数溢出问题。这道题里高度最大值不会超过10^4宽度也不会特别离谱int足够。但如果数组元素范围是10^9级别比如某些变体题Long或者大数类型就要考虑进来了。3.3 代码里的三个易错点我全踩过第一个易错点是在更新面积前就移动了指针。比如想当然写成left再算面积你会发现宽度少了1结果完全不对。正确顺序必须是先根据当前left和right计算面积并更新答案再移动指针。第二个易错点是循环终止条件写成left right。当left right时左右指针指向同一根柱子容器宽度为0虽然面积也是0不影响最终答案但逻辑上已经没有意义了。建议统一用left right语义更清楚。第三个易错点在移动指针时的条件判断写反写成if (height[left] height[right]) left。这个错误尤其隐蔽因为当数组是递增序列时这种写法有时候也会碰巧算出正确答案但整体逻辑是错的遇到随机数组就会挂。移动矮侧是铁律别凭感觉改。4. 这类题的识别套路怎么知道该用双指针4.1 双指针题型的典型特征画像很多人刷题靠“背模板”但真正高效的方式是建立“条件反射”。哪些题应该考虑双指针我总结出几个信号第一题目涉及两个元素之间的某种关系比如总和、差值、面积、距离、最大水容量。第二暴力解是O(n^2)的双重循环且数据范围在10^5以上。第三数组本身无序或者说不依赖排序就能通过“移动端点”的方式来缩小搜索空间。第四计算出的某个值只由两个端点决定中间元素不影响结果。这题完美符合以上所有特征。一旦识别出来就能快速判断不是哈希表方案、不是排序方案、不是动态规划方案而是相向双指针。4.2 相向双指针 vs 同向双指针怎么区分双指针分两大流派相向双指针和同向双指针。相向双指针就是这题用的左右两端向内收缩常用于数组有序或半有序场景下的两数之和、回文判断、盛水容器等。它的核心是“每次排除掉一边的无效区间”所以必须能证明被排除的那一侧不可能产生更优解。同向双指针也叫滑动窗口两个指针都从左往右走常用于满足某种条件的连续子数组问题比如“长度最小的子数组”(LeetCode 209)、“无重复字符的最长子串”(LeetCode 3)。它的核心是“维护一个窗口通过右指针扩大、左指针收缩来寻找可行解”。区分方法很简单两端收缩排除的是“区间外不可能”是相向一端扩张一端收缩维护的是“当前窗口合法性”是同向。这题是前者因为不存在“窗口”的概念讨论的永远是最外侧两条线。4.3 与相邻模板题的对比接雨水与最大矩形盛水最多的容器(11)、接雨水(42)、最大矩形(85)经常被放在一起比较。它们的共同点是都涉及“柱子”和“面积”但解法思路完全不同。接雨水是计算所有凹陷处能存的雨水总量用的是单调栈或者左右最高柱子的“前缀最大/后缀最大”思想。它关注的是每个位置上方能存多少水依赖两侧最高柱子的较小值减去当前高度。最大矩形柱状图中最大的矩形则是在直方图里找面积最大的矩形核心是单调栈找每个柱子左右两侧第一个比它矮的位置以当前柱高为矩形高。盛水容器则只关注两堵墙之间的最大面积双指针直接在端点收缩即可完全不需要单调栈。我在复习的时候会把这三题放到一起看对比它们的“面积计算方式”和“数组遍历方式”这样印象会深很多。有读者问过我为什么接雨水不能用盛水容器的双指针解法因为接雨水关心的是所有位置的水量累积而盛水容器只关心一对墙的极值。目标函数不同对应算法自然不同别看到“柱子面积”就往一个模板里套。5. 常见问题与排查技巧实录5.1 新手最容易犯的4个错误附排除方法这里直接上我刷题和看群友提问时汇总的常见问题速查表。问题现象根因排查/修正方法输出结果比预期小先移动指针后计算面积宽度少了1调整代码顺序务必先算面积再动指针输出结果比预期大把height[left]和height[right]中大的那个当成了容器高度检查是否用了Math.max而不是Math.min部分用例超时误用了O(n^2)暴力解法换双指针确认循环里每次只移动一个指针数组长度为2时答案错误边界初始化或循环终止条件写错单步调试确认left0, rightn-1, while(leftright)这些错误里“把Math.max写成Math.min”是尤其常见的因为很多人看到“最多”两个字就不自觉把面积里的“高度”也取大了。请记住面积 最小高度 × 宽度这个最小高度是不能用“最大化目标”替代的。5.2 从周赛430看命题趋势双指针还能怎么考最近LeetCode周赛430里有几道题也涉及了双指针的变形比如需要结合哈希表记录出现的次数或者结合前缀和做预处理。这说明双指针很少单独出现它更像是一个“基础骨架”常常要跟其他数据结构组合使用。举例来说如果题目改成“求最大面积但要求两条墙的下标差不小于k”你仍然可以用双指针只是在更新答案时加一个if (right - left k)的判断。再比如“求水的体积但墙体本身有厚度”那就需要给宽度部分减去墙体的实际厚度核心逻辑完全不变。我在备战周赛时习惯把这类题归纳为“双指针 条件剪枝”。建议读者在刷题时不满足于AC一道题多做一步变形思考如果数组有序能用吗如果要求返回下标呢如果允许修改数组呢这些都会显著提升你的应对能力。5.3 面试讲解这题的口径与实战心得如果在面试里遇到这题代码写出来只是第一关你需要把思路讲清楚。我建议按这四步来组织语言第一步说明暴力解法的局限。可以说“最直观的做法是枚举所有左右边界组合复杂度是O(n^2)在n较大的情况下不可行。”第二步指出现象。说“我们发现当左右指针指向两根柱子时容器的高度取决于较短的那根。如果将较长端向内移动宽度减小且高度不可能增加因此面积必然减小。所以移动较矮端才有意义。”第三步给出证明。“每次移动较矮端相当于排除了所有以它为边界的候选组合因为其中任一组合的面积都被当前面积上界限制。”第四步给出复杂度。“左右指针最多各移动n次总体O(n)时间O(1)空间。”这套讲法既体现了你的算法功底也展示了数学证明能力比上来就甩代码要加分得多。我自己面试候选人的时候只要对方能讲到第三步的证明这道题基本就给过了。最后再分享一个小技巧我在LeetCode上刷到这道题时学到的不仅是双指针更重要的是“如何证明贪心选择的正确性”。此后我遇到类似问题都会刻意追问自己一句——这一步贪心会漏掉最优解吗这个习惯帮我解决了很多难题也让我的刷题效率提升了一大截。