刷LeetCode的人迟早会和《盛最多水的容器》打个照面。这道题编号是第11题看起来很直观实际上考的是你对“搜索空间压缩”的理解一个数组里任意两个位置围出来的矩形面积怎么在最短时间内找到最大。我第一次做这题时第一反应就是两层循环把所有组合算一遍觉得这不就完事了后来看到双指针解法恍然大悟但真让自己把“为什么移动短边不会漏掉答案”讲清楚还是卡了壳。这篇文章就把这题的数学模型、双指针原理、代码实现、常见坑和面试表达一起拆开讲适合刚准备算法面试的人也适合已经刷过一遍但还想加深理解的人。1. 题目到底在问什么把“盛水”翻译成数学模型1.1 从题目描述到数组坐标题目会给你一个整数数组height数组的长度表示有这么多条竖线下标i是横坐标height[i]是这条竖线的高度。你要在这个二维坐标系里选两条竖线和 x 轴一起组成一个“容器”容器能装多少水取决于两块板里较短的那块板的高度再乘以两块板之间的水平距离。数学表达式就是面积 min(height[i], height[j]) * (j - i)注意下标j i。这就是水桶效应在算法题里的呈现能装多少水不由最长的那块板决定而由最短的那块板决定。这个公式如果你自己在纸上画几个矩形会特别有体感。官方示例里那个数组是[1,8,6,2,5,4,8,3,7]答案是 49。为什么是 49因为下标 1 和下标 8 对应的高度分别是 8 和 7距离是 7短边是 7面积就是7 * 7 49。这个例子后面可以用来验证代码。这里我建议先别急着看答案而是拿出纸笔画一个数组把每根竖线画出来。你会发现这题虽然叫“盛水”但本质就是个几何面积最大问题和你想的“容器是不是封闭”“水会不会漏”完全没关系。题目看重的是数学抽象能力。1.2 先看最朴素的双层循环思路对于刚接触算法题的人来说最容易想到的就是枚举所有可能的两根竖线组合。两层 for 循环外层枚举左指针i内层枚举右指针j每次计算面积不断更新最大值。用伪代码写就是ans 0 for i in range(n): for j in range(i 1, n): area min(height[i], height[j]) * (j - i) ans max(ans, area) return ans这段代码本身没什么错误结果一定是对的。问题出在复杂度组合数量是n * (n - 1) / 2也就是 O(n²)。LeetCode 的约束通常把数组长度拉到 10 的 5 次方级别O(n²) 要算 10 的 10 次方次现代机器也很难在限定时间内跑完。暴力解法虽然超时但它在面试里其实有它的价值。你可以先说出这个最自然的思路让面试官知道你能理解问题然后再提出优化方案展示你具备从坏方案走向好方案的能力。最怕的是上来就默写双指针但又说不清楚为什么这在面试中反而会暴露理解深度不够。1.3 直觉是怎么来的从最宽处开始收缩为什么双指针能在 O(n) 时间内解决问题核心直觉是这样先把两根指针放在数组最左和最右这时候宽度最大面积是min(height[left], height[right]) * (n - 1)。接下来如果想把面积变大宽度只会越来越小所以必须让“短边的高度”尽量提高。假设height[left] height[right]也就是短板在左边。现在你面临两个选择移动左指针还是移动右指针如果移动右指针那么新的右指针不管多高容器的高度仍然被左边的短板限制甚至可能更矮同时宽度还变小了所以面积不可能变大。反过来移动左指针还有机会遇到更高的左边竖线从而突破刚才那个高度瓶颈。这个思路不需要严谨证明也能让人快速接受。双指针解法不是凭空冒出来的它来自对面积公式“宽度在减少高度只能看短边”的观察。先把这层直觉建立起来后续看证明会舒服很多。2. 双指针核心原理与正确性证明2.1 指针移动规则与代码骨架双指针的做法很固定先贴一个核心骨架left 0 right n - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1每次循环只做两件事计算当前两根指针形成的面积然后移动高度较小的那一根指针。如果两边高度相等移动哪边都可以不会影响最终答案。这个代码骨架第一次看会觉得很神奇明明有 O(n²) 种组合为什么只移动指针就能找到最优解其实关键在于每一次移动都“剪掉”了一整批不可能成为答案的候选组合而不是只排除了当前这一种组合。理解这一点才算真正懂了双指针。2.2 为什么移动“较短边”一定安全一个不等式证明这里我还是想用数学方式把“移动短边不漏答案”这件事讲透。假设当前左指针是i右指针是j并且height[i] height[j]也就是左边是短边。当前面积是min(height[i], height[j]) * (j - i) height[i] * (j - i)现在如果保持i不动让右指针向左移动到任意位置k其中i k j那么新面积是min(height[i], height[k]) * (k - i)因为不管height[k]是多少min(height[i], height[k])一定小于等于height[i]同时k - i j - i。所以这个新面积一定严格小于当前面积。换句话说在当前这一轮里任何“以i为左边界右指针往左挪”的候选组合都不可能超过当前这个面积。因此我们可以放心地把左指针向右移一位丢掉所有以i为左边界但还没被检查过的组合因为它们已经被证明不会成为全局最优。另一边高度相等时也一样min的结果都被短板限制宽度又在减少所以移动任意一边都可以。这个证明的实质就是双指针不是用暴力遍历所有状态而是利用“面积公式具有单调限制”这一性质成片地排除无效状态。能在面试中说出这一步基本就比只会背代码的人高出一个段位。2.3 复杂度分析从 O(n²) 到 O(n) 的搜索空间压缩双指针整个过程里left只能向右移动right只能向左移动两个指针一共移动n - 1次就会相遇所以只计算了n - 1种候选状态。每次计算面积和比较更新都是 O(1)时间复杂度就是 O(n)额外空间只有两个整数空间复杂度 O(1)。这里有人会问只检查n - 1种状态凭什么不漏答案答案就在上一节的证明里每移动一次指针我们就排除了一个“不可能成为最优解”的区间集合。相当于把 O(n²) 的搜索空间按规则剪枝剪到最后只需要看一条路径上的状态而全局最优就藏在这条路径上。这种搜索空间压缩的思想比这道题本身重要得多。以后你会遇到很多看似需要枚举的题其实都可以用“单调性剪枝”来优化。遇到这类题先想想能不能让两个指针按某种方向单调移动往往就离正确解法不远了。3. 代码实现与调试细节3.1 Python 和 C 版本Python 版本写起来非常简洁def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ansC 版本要注意下标类型和vector的访问class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int h min(height[left], height[right]); int w right - left; ans max(ans, h * w); if (height[left] height[right]) { left; } else { --right; } } return ans; } };两个版本的逻辑完全一致。我建议初学者在本地编辑器里把输入输出部分补全随便造几个数组跑一跑加深印象。直接在网页上提交虽然也能学但手动调试一遍收获会大很多。3.2 几个容易写错的细节第一个细节宽度是right - left不是right - left 1。两根竖线的宽度等于它们下标的差值。比如左边在下标 1右边在下标 8中间隔了 6 个位置宽度就是 7。很多人受“数组长度 下标差加一”的影响这里容易多算 1。第二个细节先算面积再移动指针。顺序如果反了当前状态就会被跳过。虽然最终答案可能不受影响因为如果当前状态不是最优跳过也没关系但这不是你写程序应该依赖的运气。逻辑正确、步骤清晰才便于排查问题。第三个细节两边高度相等时不要想着“两边一起移”。同时移动两边可能会漏掉最优解。比如某个最优组合恰好用到了当前的两块等高木板中的一块你一手一个同时跳过就把这条候选路径丢掉了。虽然前面证明过移动任意一边都安全但“两边都移”并不在安全证明范围内别自作聪明。第四个细节在 C 里如果height.size()返回的是size_t你可能需要留意无符号类型和int混用的问题。LeetCode 的数组长度不会大到离谱但更好的习惯是直接使用int left 0, right (int)height.size() - 1;避免后续比较出现类型警告。3.3 手动跑一个例子验证你的代码我来手动模拟[1,8,6,2,5,4,8,3,7]的开头几步方便你对照。初始left0, right8高度是 1 和 7面积是min(1,7)*8 8更新ans8。因为height[0] height[8]移动左指针到 1。接着left1, right8高度是 8 和 7面积是min(8,7)*7 49更新ans49。此时height[1] height[8]移动右指针到 7。再下一步left1, right7高度是 8 和 3面积是min(8,3)*6 18小于 49不更新。height[1] height[7]移动右指针到 6。之后left1, right6高度是 8 和 8面积是min(8,8)*5 40还是小于 49。两边相等按代码会移动右指针到 5。后面继续走到结束最后答案就是 49。建议你也自己把整个过程推完不要只停在这几步。手动推演会让“指针为什么往这边走”变得非常有画面感比看十遍题解都管用。4. 常见问题与排查技巧4.1 为什么我的双指针结果不对常见的问题无非这几种结果偏大、结果偏小、死循环。结果偏大大概率是宽度算错了用成了right - left 1把边界上的距离虚拟地多加了一单位。结果偏小可能是更新ans的时机不对或者把移动指针写在了计算面积之前。死循环则多半是while里的left right条件写成了left right或者指针移动语句被忘在了条件分支外面。排查这些问题的办法非常朴素在循环里打印left、right、area、ans四个值。一旦出现某个面积骤减但指针没有按预期移动你立刻就能看到原因。算法题排错不一定要靠调试器最简单的日志输出往往最有效。还有一种隐蔽错误比较高度时用了两边相等时移动左指针下一次循环里如果两边还是相等又移动左指针。这其实是安全的不会漏解。真正的不安全操作是同时移动两边指针这点前面强调过建议在写代码时用注释明确标记一下“只移一边”。4.2 这题和“接雨水”到底有什么区别很多人刷题时会把《盛最多水的容器》和《接雨水》放在一起做然后越做越混。其实它们的计算目标完全不同这题是让你在数组里选两条竖线围成一个矩形容器问容器最大能装多少水而“接雨水”是让你算整个数组形成的“山谷”地形在每一格凹陷处能接住多少雨水最后把所有凹陷处的水量加起来。可以这样理解盛水容器是一个“孤儿”容器只考虑两根柱子接雨水是一个“连片”地形要考虑整条轮廓线。接雨水的常见解法有单调栈、双指针和动态规划双指针思路虽然也有但逻辑比这题复杂很多因为要分别维护左边最大高度和右边最大高度。建议不要在同一天连续刷这两道题除非你有意对比。否则很容易把“移动较低边”的容器解法套用到接雨水里导致状态算错。先把容器这题彻底搞懂再去做接雨水你会感觉思维是递进的。4.3 面试时怎么把这题答成加分项面试官如果问你“怎么做”不要只甩出双指针代码而是按这个顺序表达先说我有一个暴力枚举思路枚举所有(i, j)组合时间复杂度 O(n²)空间 O(1)。然后说进一步观察面积公式min(height[i], height[j]) * (j - i)当宽度收缩时只有提高短边才有机会让面积变大。于是可以用两个指针从两端向中间移动每次移动较短的边因为较短边限制了当前容器的高度移动较长边不可能让面积增大。最后补充一句正确性证明如果左边界是短边那么所有以它为左边界、右指针继续向左的组合面积都会被当前面积压倒所以可以安全排除。这个回答最加分的地方是证明那一段。很多人能写代码但说不出“为什么”一旦你能用不等式把剪枝逻辑讲清楚面试官很容易判断出你是真懂而不是背题。最后还可以主动提一下边界情况比如数组长度小于 2 时返回 0时间复杂度 O(n)空间 O(1)。整个回答控制在 3 分钟左右最合适。5. 双指针思想与个人刷题心得5.1 双指针还能用在哪些场景“盛最多水的容器”是双指针思想的一个绝佳载体。类似的两端向中间移动的双指针题还有很多比如有序数组的两数之和、判断回文字符串、反转数组、三数之和里的去重逻辑等。它们的共同特征是状态空间是一个二维矩阵但每走一步都能根据单调性排除一整行或一整列。我给一个经验判断如果你发现题目是“在一个数组里找两个元素满足某个条件并且条件随着两个下标的距离变化存在单调性”就可以试试双指针。不用硬背而是反复体会“排除不可能域”的本质。双指针还有另一种形态就是快慢指针常用于链表问题比如判断链表是否有环、找链表中点。虽然形式上不是左右夹逼但思想依然是“用不同速度的指针在某种结构上移动减少不必要的重复扫描”。学会了这题的左右指针再碰快慢指针就不会觉得陌生。5.2 踩过坑之后的几点体会我在实际刷题中最大的体会是不要以为自己看懂了题解就真的会了。尤其是双指针这种“代码短到不像算法题”的类型特别容易让人产生“我懂了”的错觉。我建议你看完题解后把页面关掉自己从头写一遍写不出来再回去看隔一天再重写。写三遍感觉完全不同。另外一个很实用的方法是“费曼学习法”把这道题的思路讲给你身边不刷题的人听或者讲给空气听。如果你能说清楚为什么移动短边不会漏答案而不是只说“因为大家都这么做”那才算过关。讲不出来就去重新看证明补上逻辑缺口。最后想提醒一点刷这种经典题不要只追求提交通过。把暴力解法、最优解法、正确性证明、复杂度分析、测试边界拉通一遍才会变成你自己的东西。一道题吃透胜过十道题走马观花。