盛最多水的容器这题代码量很小核心循环也就五六行但它在 LeetCode 热门 100 题里的地位挺特别——如果你去面试考官让你写这道题很多人能流畅背出双指针的解法可一旦被追问为什么每次都移动矮的那根柱子而不是高的那根就当场卡壳。能把这个问题回答清楚的人才是真正吃透了双指针。这篇文章我按自己刷题复盘的方式来写先把题面翻译成数学问题再讲清楚双指针收缩背后的正确性证明接着给完整的实现代码和一手的踩坑记录最后聊聊它和接雨水、三数之和这些亲戚题的关系。适合正在刷 LeetCode 热门 100 题、准备面试算法轮次或者觉得自己会写代码但讲不清思路的朋友。1. 题面翻译把能装多少水变成一道纯几何题1.1 原始题面与第一印象题面描述是这样的给定 n 个非负整数 height[0], height[1], ..., height[n-1]每个数代表坐标 (i, height[i]) 处的一条垂线。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水返回最大水量。说白了就是给你一堆高度不同的墙让你选两面墙围成一个容器问最多能装多少水。注意这里的水在二维平面里就是一个矩形面积不涉及三维体积。很多第一次做这道题的人会把它和 42 题接雨水搞混但这两者有个本质区别11 题只需要选两条线中间那些墙完全不影响答案而 42 题是把所有柱子之间能存的雨水全部加起来。这个区分很重要我后面专门有一节讲。第一眼看到这道题最容易联想到的是最大矩形面积底边是两根柱子的水平间距高度受限于较矮的那根。脑子里有这张图后面一切都顺了。1.2 容器面积公式min(height[l], height[r]) × (r - l)设左墙在 i右墙在 ji j那这个容器能装多少水就由两个因素决定宽度两根柱子的水平距离也就是 j - i高度两根柱子中较矮的那一根的高度也就是 min(height[i], height[j])。所以目标函数就是area(i, j) min(height[i], height[j]) × (j - i)这里最容易犯的错是直接拿 height[i] × height[j] 当面积忽略了短板效应。你可以把容器想象成一个 U 形水槽两边高度不一样往里倒水水一定从矮的那边溢出去所以水面最高只能到矮边的高度。这就是短板效应——容器能装多深的水永远取决于矮的那面墙。理解了 min 的含义这道题的暴力解法就自然而然地出来了。1.3 暴力解法能想到但撑不住最直觉的解法是双重循环枚举所有两根柱子的组合def maxArea(height): n len(height) 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这个解法正确性毋庸置疑但复杂度是 O(n²)。题目里 n 最大能到 10^5那就是 10^10 次运算在力扣上直接超时。我的建议是面试的时候先写暴力解确认题意理解无误然后再顺势说但是 O(n²) 在数据量大的时候不可行我观察到宽度和高度之间存在单调性可以优化成 O(n)。这是标准的做题节奏——先证明你理解题目再展示优化能力。如果上来就甩双指针反而容易被面试官怀疑是不是背题。2. 双指针收缩策略为什么移动矮墙一定不会错过最优解2.1 指针从哪里出发双指针的第一步是把左指针 l 放在最左边右指针 r 放在最右边。为什么要从两端开始因为这时候宽度是全局最大的n-1底边最长。宽度大不代表面积大因为高度可能被很矮的墙锁死但至少这是一个合理的起点。拿官方示例 [1,8,6,2,5,4,8,3,7] 来说一开始 l0高度是 1r8高度是 7。面积 min(1,7)×8 8非常小。为什么因为左边第一根柱子只有 1 高右墙再高水面也只能到高度 1。这时候我们面临一个选择下一步该移动左指针还是右指针2.2 移动高墙为什么是无效操作继续看刚才的例子。现在 height[l] 1height[r] 7左墙是矮墙。如果移动右墙高墙把 r 从 8 挪到 7宽度从 8 变成 7左墙高度仍然是 1那么新面积 min(1,3)×7 7比之前的 8 还小。继续往左挪不管右墙移到哪里面积都不会超过 1 × (r - l)因为左墙的 1 就是天花板。这里可以总结出一条规律当 height[l] height[r] 时容器高度已经被 height[l] 锁死右墙无论挪到哪里高度上限都不会超过 height[l]宽度却在不断缩小。所以以当前右墙为候选的所有更小的右端点全部可以被安全否定。反过来也一样当 height[r] height[l] 时移动左墙是无效的唯一有希望的方向是移动矮墙。2.3 反证式推理每一步都在排除无效候选光有直觉还不够面试时得能给出严谨的推理。设当前 l r且 height[l] height[r]那么当前面积S height[l] × (r - l)考虑任何一个右端点 r满足 l r r。这个新面积S min(height[l], height[r]) × (r - l)因为 height[l] 是左边那个固定的矮墙所以 min(height[l], height[r]) ≤ height[l]同时宽度 (r - l) (r - l)因此S ≤ height[l] × (r - l) S这说明固定左端点 l 的时候所有在 r 左边的右端点都不可能超过当前面积。所以当前这个左端点 l 已经被榨干了可以放心地向右移动 l去尝试新的左端点。每一步都排除掉一个绝不可能是最优解的端点那么双指针扫描完整个区间后所有可能成为最优解的组合都被覆盖到了。这就是双指针对这道题的正确性来源。如果你能在面试里把这个逻辑说出来这道题基本就过关了。2.4 一个常见的错误优化念头有些人会想既然移动矮墙才有希望那我能不能一次跳到位比如直接把矮墙跳到比当前矮墙更高的位置这个想法理论上可行跳过的高度必然 ≤ 当前矮墙高度的位置确实不可能产生更优解。但在实际编码里很容易翻车。我自己就写过这种跳过优化结果在 [1,2,3,4,5] 这种单调递增的数组上基准高度没更新对指针一直跳不到头直接死循环。想明白之后我觉得这道题的复杂度本来就是 O(n)一次跳一步和跳几步在常数上差别不大但代码的正确性和可读性差别很大。老老实实一步一步走是最稳的写法。在面试现场稳定输出比炫技重要得多。3. 完整实现与运行过程模拟从代码到每一步的推导3.1 三种主流语言的核心实现先给出三种常用语言的写法。核心逻辑就四步进入循环、算面积、更新答案、移动矮边。Pythonclass Solution: def maxArea(self, height: List[int]) - int: l, r 0, len(height) - 1 ans 0 while l r: area min(height[l], height[r]) * (r - l) ans max(ans, area) if height[l] height[r]: l 1 else: r - 1 return ansJavaclass Solution { public int maxArea(int[] height) { int l 0, r height.length - 1, ans 0; while (l r) { int area Math.min(height[l], height[r]) * (r - l); ans Math.max(ans, area); if (height[l] height[r]) { l; } else { r--; } } return ans; } }Cclass Solution { public: int maxArea(vectorint height) { int l 0, r height.size() - 1, ans 0; while (l r) { int area min(height[l], height[r]) * (r - l); ans max(ans, area); if (height[l] height[r]) l; else --r; } return ans; } };注意一个细节当 height[l] height[r] 时代码走的是 else 分支也就是移动右指针。其实这种情况下移动哪边都不影响最终结果但统一写成小于移左否则移右最不容易出错。下面模拟运行时会看到。3.2 手跑一遍示例数组用官方的示例 [1,8,6,2,5,4,8,3,7] 来模拟一遍。ans 初始为 0我们记录每一步的状态步骤lrheight[l]height[r]较矮高度宽度面积ans108171888218877749493178336184941688854049515844416496148553154971382224498128661649第 9 步时 l 1r 1循环条件 l r 不满足退出。最终答案是 49与官方输出一致。看这张表能直观感受到最大面积 49 出现在第 2 步也就是 l1高度 8和 r8高度 7这一对组合。之后无论指针怎么移动都没能突破 49。更重要的是在这个过程中所有被跳过的端点都是被第 2 章的逻辑证明过不可能更优的不是随机丢弃的。3.3 变量的类型范围与循环边界几个容易被忽略的工程细节循环条件必须是 l r而不是 l r。l r 时只剩一根柱子不能构成容器min(height[l], height[r]) 也没有意义。数据范围n ≤ 10^5height[i] ≤ 10^4最大面积是 10^4 × (10^5 - 1) ≈ 10^9int 的范围是 2^31 - 1 ≈ 2.147×10^9刚好装得下。但如果题目改大数据范围比如 height 到了 10^9Java/C 里就该用 long 或 long long 了。Python 没有溢出问题。如果 height 为空或者长度小于 2理论上不会出现因为题面保证 n ≥ 2。但写一个防御性判断也不亏面试时体现的就是工程素养。4. 从这道题延伸出去双指针题型家族与识别信号4.1 42. 接雨水从选两条线到统计每个位置很多人在刷完盛最多水的容器之后紧接着刷 42. 接雨水。这两题表面长得像实际解法不同对比项11 盛最多水的容器42 接雨水目标选两条线使围成的矩形面积最大统计所有柱子之间凹槽能存多少水双指针移动规则移动较矮的一侧移动左右最大值较小的一侧需要维护的变量只要当前两根柱子的高度需要 leftMax 和 rightMax返回值一个最大面积值累计水量42 题的核心思想是对于位置 i它能存的水量 min(左侧最高柱, 右侧最高柱) - height[i]如果这个值是正数就累加。双指针解法通过动态维护左最大值和右最大值避免了为每个位置重新扫描左右两侧。把 11 题吃透之后再去看 42 题你会觉得双指针不再是背模板而是真的能推出来。4.2 三数之和同一种思想的不同运动规则15 题三数之和是另一个经典双指针题先排序固定一个数剩下两个数在区间内用双指针相向移动根据 sum 和目标值的关系决定移动方向。和 11 题相比三数之和的双指针移动规则是sum 大了就右指针左移sum 小了就左指针右移这是因为数组有序移动方向对应数值的单调变化。而 11 题不能排序——排序会破坏柱子的原始位置关系而宽度恰好依赖这个位置关系。但两者的共性非常明显利用某种单调性在每一步排除掉一部分无效组合把二维枚举压缩成一维扫描。脑子里建立起这个框架刷双指针题会轻松很多。4.3 识别双指针题型的三个信号根据我的经验一道题是否适合用双指针可以从三个信号判断暴力解法是 O(n²) 的二维枚举n 在 10^5 这个量级直接枚举会超时目标表达式中包含两个下标的位置差比如 min/max × (j - i)或者需要两个元素之间的关系比如和为 target移动某一端之后可以用高度上限被锁死或有序单调的逻辑快速排除一段区间。不是说满足这些信号就一定用双指针但当你带着这个意识去看题通常会比毫无方向地硬想更快找到思路。这就像修车老师傅听发动机声音——听多了自然知道是哪里的问题。5. 面试现场复盘与刷题心得那些背代码学不到的东西5.1 面试官追问的三个高频问题这道题在面试里出现频率很高而且面试官几乎一定会追问。我总结三个最常见的问题问题一为什么移动矮边而不是移动高边标准回答容器的盛水高度由矮边决定。移动高边时新的容器高度不可能超过原来的矮边高度而宽度一定减小所以面积只会变得更小。只有移动矮边容器高度的上限才有机会提高面积才有可能变大。这句话就是整道题的灵魂。只要能把这个说出来面试官就信你是真懂。问题二height[l] height[r] 时怎么办此时两边一样高容器高度已经是这两根柱子之间能到达的极限无论移动哪一边新高度都不超过当前高度宽度又必然减少面积都会变小。所以哪边都可以。代码里写成 if height[l] height[r] 就左移否则右移让相等情况统一走右移逻辑最简单。问题三时间复杂度是多少O(n)每个指针最多移动 n 次两个指针合计 O(n)空间复杂度 O(1)。5.2 刷题过程中真实踩过的坑我自己刷这道题时踩过几个坑写出来帮大家避开。第一个坑是跳过优化导致的死循环这个前面说过不再重复。核心教训是不要为了常数级别的优化牺牲代码的确定性。第二个坑是把 ans 的更新写在指针移动之后。这样会漏掉初始状态下的面积比如第一步宽度为 n-1 时那个面积就没了。正确顺序是进入循环先算面积、更新 ans再决定移动方向。第三个坑是相等分支写漏。如果写成 if (height[l] height[r]) l; 然后又用 if (height[l] height[r]) r--这没问题但如果写 if-else if 后漏掉相等的情况指针会停在原地死循环。最稳的写法就是上面代码里那样小于就左移否则就右移。第四个坑比较隐蔽有人试图先对数组排序再用双指针。这是不对的因为两条线的宽度依赖它们在原数组中的下标差排序会彻底摧毁宽度信息相当于改变了题目本身。5.3 记忆锚点与滚动复习节奏刷题社区里很多人问这道题老是忘怎么办。我的建议是给自己设记忆锚点不要背代码要背一句话容器高度被矮边锁死移动高边只能让情况更差。这句话能推演出整个双指针解法。复习节奏上我的习惯是第一次刷完隔一天必须重做一遍目标是 5 分钟内 AC如果隔一周还能独立写出来并且能讲清楚为什么移动矮边才算真正掌握。热门 100 题里的双指针题目我推荐的刷题顺序是11盛最多水的容器→ 42接雨水→ 15三数之和→ 283移动零→ 76最小覆盖子串。前四个是相向或同向双指针最后一个是滑动窗口变体难度依次递增衔接比较自然。最后说点个人体会。我大概是刷到第四遍的时候才真正想明白移动矮边不仅仅是一个策略更是一条能严格推理的正确性论证。从那以后遇到双指针题我就没那么慌了因为我清楚双指针不是玄学它是一种用单调性把二维枚举压缩成一维扫描的思维方式。如果你刷这道题时也觉得代码很简单但道理说不清那是正常的把上面第二节的推导自己动手写一遍写到能给别人讲明白的程度这道题才算真正过了。祝你刷题顺利。
