要说算法面试里哪个题目最能检验数组功底我第一个想到的就是接雨水。题目本身一句话就能说清给出一列非负整数表示每根宽度为1的柱子的高度求下雨后它们能接住多少水。可就是这么个简洁的题既可以用暴力硬解也可以用动态规划预处理更可以压缩成双指针的短短十几行代码。很多人在这一步卡住不是看不懂代码而是没想明白“双指针怎么知道每根柱子左右边界的高度”。这篇文章专门拆双指针这条思路从水量公式讲到状态推演、调试心得和面试应答希望能把你彻底教会。1. 先拆解接雨水的核心公式再谈双指针1.1 一个位置能接多少水先把公式写出来先别急着看算法把物理模型翻译成数学表达式这题的根就在这。假设柱子高度数组是height长度为n。每个位置i占宽度 1它上方能不能积水取决于左右两边有没有更高的柱子。水是往低处流的所以一个位置的水面高度会被它左侧所有柱子中的最高值和右侧所有柱子中的最高值中较小的那一个封顶。这句话是“木桶原理”的翻版一个位置能养住多少水不取决于最高的那面墙而是取决于最矮的那面墙。于是就有公式water[i] min(左侧最高, 右侧最高) - height[i]注意这里的“左侧最高”和“右侧最高”都包含height[i]自己。这么做有个好处min(左侧最高, 右侧最高) height[i]恒成立所以water[i]永远非负不需要再包一层max(0, ...)。用[2, 0, 2]验证一下中间位置 i1左最高是 2右最高是 2min(2, 2) - 0 2所以能接 2 格水。而端点 i0左最高是 2右最高是 2min(2, 2) - 2 0自然不用管因为水会从两边流走。这个公式是后面所有解法的基础。暴力法直接用它动态规划预处理也是用它双指针只是把它算得聪明一点而已。物理上水面是连通的但总量恰好等于每个柱子正上方水柱高度的累加这就给了我们逐格计算的空间。1.2 暴力法先跑通O(n²) 的代价有了公式第一版代码几乎是翻译def trap_brutal(height): n len(height) if n 3: return 0 ans 0 for i in range(1, n - 1): left_max max(height[:i 1]) right_max max(height[i:]) ans min(left_max, right_max) - height[i] return ans从1到n - 2遍历跳过头尾两个端点因为最左和最右外侧没有挡板公式套上去也是 0没必要算。每个位置都取一次左侧最大值和右侧最大值直接套公式累加。这个解法完全正确但效率很差每个位置都要向左向右各扫一遍总复杂度是 O(n²)。面试时作为第一版答案没问题甚至我建议你第一版就这么写既能让面试官看到你的思路起点也能给自己后面的优化铺路。1.3 暴力慢在重复扫描预处理是怎么救场的暴力法的问题在于信息浪费算 i 位置时扫了[0..i]算 i1 位置时又扫了[0..i1]中间大量重叠区间被反复遍历。最容易想到的优化是预处理两个数组从左到右扫一遍记录每个位置的左侧最高从右到左扫一遍记录每个位置的右侧最高。这样每个位置的左右最高都能在 O(1) 时间内得到。left_max [0] * n right_max [0] * n left_max[0] height[0] for i in range(1, n): left_max[i] max(left_max[i - 1], height[i]) right_max[n - 1] height[n - 1] for i in range(n - 2, -1, -1): right_max[i] max(right_max[i 1], height[i]) ans 0 for i in range(n): ans min(left_max[i], right_max[i]) - height[i]时间降到 O(n)但空间变成 O(n)要用两个数组把左右信息存下来。到这里很多人觉得已经不错了但面试官下一句话往往就是“能不能把空间也省掉”双指针就是冲着这个来的。2. 双指针的核心推导为什么矮的一侧必须先结算2.1 一左一右两个指针各自维护“见过的最高墙”双指针的思路和预处理完全不同。预处理是先把所有位置的左右最高算好再统一求答案双指针则是在向中间收缩的过程中当场把一部分位置结算掉。具体做法是左指针从最左出发右指针从最右出发。两个指针一边向中间走一边各自记下自己这一侧已经见过的最高柱子left_max从height[0]到height[left]的最大值right_max从height[right]到height[n-1]的最大值。每次比较height[left]和height[right]哪边矮就结算哪边当前这个位置然后把指针往中间挪一步。这个过程像两个人从堤坝两端相向巡查各自记着这段路上见过的最高坝谁脚下的地势低谁先确定自己头顶的水面高度。2.2 核心证明为什么可以放心结算矮的一侧这是整篇最关键的逻辑也是双指针解法最容易被一带而过的地方。看左指针的情况。当height[left] height[right]时对于位置left来说第一它右边至少有一根柱子高度是height[right]而且height[right]比height[left]更高。所以右侧的真实最高值一定大于height[left]。第二left_max是左侧已经扫过的所有柱子加上当前height[left]里的最高值。问题在于这个left_max会不会特别高高到右侧的真实最高值都比不上它答案是不会。因为左指针能走到当前位置说明它每跨过一根柱子的时候当时右边都有一根比这根柱子更高的柱子立在那否则那次比较就不会让左指针前进。也就是说左侧扫过的所有柱子都已经被右侧某个更高的柱子“罩住”了。因此右侧的真实最高值一定不小于left_max。把这两点合起来右侧最高值既大于当前height[left]又不小于left_max那么min(left_max, 右侧真实最高)就等于left_max。于是可以直接用left_max - height[left]结算左指针当前位置完全不需要看到右侧全貌。右侧的情况完全对称当height[right] height[left]时右侧扫过的最大值一定不大于左侧真实最高值所以用right_max - height[right]结算是安全的。提示这个“右侧真实最高值不小于 left_max”的结论是整个双指针解法的命根子。不在乎它代码只是死记硬背想通它你才能应对面试里的临场追问。很多人初看这题会觉得双指针怎么能不看看右边最高的柱子就乱算呢其实它不是不看而是“历史已经替你看过了”左边每一根被跨过的柱子在跨过的那一瞬间已经用比较动作确认了右侧存在更高的墙。2.3 双指针 vs 动态规划 vs 单调栈一张表看懂取舍接雨水的解法不止一种面试时把它们横向比较一下会显得你理解得很完整。解法时间复杂度空间复杂度特点暴力O(n²)O(1)直观但重复扫描过多只适合热身动态规划/预处理O(n)O(n)三个循环各做各的最容易理解和证明双指针O(n)O(1)代码最短空间最优理解门槛也最高单调栈O(n)O(n)适合处理更复杂的变体比如二维接雨水单调栈在接雨水里也是正统解法维护一个从栈底到栈顶递减的栈遇到比栈顶高的柱子就弹出并结算一段水。它的好处是能直接还原每段“凹槽”的左右边界对于扩展题更强。但这个题要求的是总量双指针在常数、空间和代码量上都更有优势面试首选双指针没有毛病。3. 双指针代码实现与状态推演3.1 不到 20 行的标准实现直接给一份可以“抄作业”的 Python 版本注释写在关键行def trap(height): if not height or len(height) 3: return 0 left, right 0, len(height) - 1 left_max, right_max 0, 0 ans 0 while left right: if height[left] height[right]: # 左边矮结算左指针位置 left_max max(left_max, height[left]) ans left_max - height[left] left 1 else: # 右边矮或相等结算右指针位置 right_max max(right_max, height[right]) ans right_max - height[right] right - 1 return ans提前判空和长度小于 3 的情况可以少处理一堆边界。其实就算不判双指针也能自然返回 0但写上会让代码更稳也显得你考虑过边界。3.2 用经典案例逐行追踪状态表光看代码还是虚拿一个标准例子[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]完整跑一遍这个例子的正确答案是 6。初始状态left 0, right 11, left_max 0, right_max 0, ans 0。步骤leftright结算侧当前高度left_maxright_maxans1011左00002111右10103110左11104210左01115310右2121639右1122738右2122837左2222947左12231057左02251167左1226最后left和right在位置 7 相遇循环结束ans 6。把几个累加的点对应回柱子看会更直观第 4 步结算的是height[2] 0它左侧最高 1、右侧也有更高的墙所以积 1 格第 6 步结算右侧位置 9 的height[9] 1它右侧已经见过的最高墙是 2水面高度 2积水 1 格第 10 步结算height[5] 0水面高度 2一次性积 2 格。每一步累加都有实际物理含义不是玄学。3.3 代码顺序的秘密几行不能乱写的细节这十几行代码每行换一下顺序结果就可能出错。这里说几个最容易踩的点第一left_max必须在本分支内先更新再累加。如果先累加再更新那么当height[left]比之前的left_max更高时累加值会变成负数因为水面高度不可能低于柱子高度。第二相等时统一走else分支。当height[left] height[right]时left和right两侧其实都能安全结算标准写法选择结算右侧。重要的是不能写if ... else if ...把相等的情况漏掉否则两个指针都不动直接死循环。第三循环条件是left right不是left right。两个指针相遇时中间那个位置左右两侧的真实最高值都已经确定了但它已经不需要结算——因为它的水量要么是 0要么在前面的步骤里被某侧提前结算过了。写成反而可能重复计算。注意代码顺序和分支条件不是小事。双指针最怕的不是思路错而是“看起来差不多”的细节导致答案莫名其妙差 1 或 2。4. 新手必看高频坑位、边界用例与面试话术4.1 五个高频错误对照表我在不同的人手里见过同一道题翻车问题几乎都出在下面这几类错误写法/习惯现象原因正确做法while left right答案偏大或运行时逻辑混乱相遇位置被重复结算用left right不判空直接len(height)空数组时崩溃边界未处理开头加if not height把两个 max 的更新都放前面右侧分支也被左侧历史污染两侧信息互相干扰各自在分支内更新if left right/else if left right/ 相等不动死循环或漏算相等情况没覆盖相等时统一走一侧用max(height[:i1])在循环内求左最高退化回 O(n²)每次都切片扫描用累计最大值变量还有一类思路性的错误有人想跳过“没有凹槽”的平缓段直接定位到某个局部最低点再开始算。这种跳跃式优化的意图可以理解但会引入大量边界判断很容易算漏。双指针的优势就是逐格推进、逐格结算老老实实走反而最稳。4.2 建议收藏的边界测试用例调试这类算法题经验是别只跑书上那个标准样例要跑一套能覆盖各种结构特征的用例。下面这组是我常用的输入期望结果覆盖点[]0空数组[1]/[1, 2]0长度不足 3[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]6经典混合地形[2, 0, 2]2最简 V 形[4, 2, 0, 3, 2, 5]9两侧最高不一致[3, 3, 3, 3]0平面无积水[1, 2, 3, 4]0单调递增[4, 3, 2, 1]0单调递减单调递增和单调递减这两个用例特别能检验你对“矮的一侧先结算”的理解单调递增时右侧一直更高所以一直在结算左指针但左指针从左往右一路走高left_max一直等于当前高度累加值恒为 0。单调递减则反过来也恒为 0。跑通这两个用例基本说明你的代码没有逻辑性偏差。4.3 面试现场该怎么讲这题如果面试官让你手写这题我建议按照下面这个路径讲既显得思路清晰又不会因为直接甩最优解而让面试官觉得你在背题。先花一分钟给出暴力版把水量公式写出来。然后提一句“这里可以用两个数组预处理左右最高时间能到 O(n)但空间是 O(n)”。接着话锋一转“能不能在移动指针的过程中直接结算呢”然后写双指针。写双指针的时候不要只念代码要把 2.2 节那个证明讲出来为什么左侧结算时敢用left_max因为height[left] height[right]保证右侧有个更高的柱子同时左侧跨过的所有柱子也都被右侧更高的墙罩住了。这一句话说完面试官基本就点头了。如果面试官追问“单调栈不也能解吗”你可以说单调栈确实能解复杂度和动态规划一样是 O(n)、O(n)而且能还原每一段的左右边界适合扩展题但接雨水求总量双指针的空间更优、代码更短所以这里选双指针。千万别接一句“单调栈解不了”那样面试官一眼就看穿你只会背一种解法。5. 从接雨水看双指针题型的通用脉络5.1 同源兄弟题盛最多水的容器和接雨水几乎共用同一套思维的是另一道经典题给定一堆柱子高度挑两根柱子问它们之间能装多少水。接雨水是每个位置都结算一遍盛水容器只求一对柱子之间的最大水量。它的双指针逻辑更直白两根柱子之间能装的水由较矮的那根决定宽度由两指针的间距决定。移动较矮的一边才有机会得到更大的面积因为移动较高的那边宽度变小而且高度不会超过原来的矮边面积必然不可能变大。这和接雨水“哪边矮先结算哪边”是同一种思想代码框架几乎一样只是累加公式不同。建议把这两题放一起练效果比单独刷要好得多。5.2 双指针家族排序数组里的三数之和双指针另一大类应用是在排序数组中做配对最典型的是三数之和问题。先把数组排序固定一个数剩下区间用左右指针向内收缩。这类题的指针移动依据是“有序性”当前和太小时左指针右移让和变大当前和太大时右指针左移让和变小。每一步移动都严格排除了一个不可能包含正确答案的方向因此不会漏解。这和接雨水里“矮的一侧先被更高墙罩住所以可以先结算”是同一件事双指针每次必须能证明某个方向的搜索区间可以安全丢弃。5.3 什么时候别用双指针双指针不是万能钥匙硬套反而会难受。如果问题需要频繁查询任意子区间的最值应该用线段树或 ST 表双指针做不到离线随机查询。如果问题需要找出每个位置左右第一个比自己高的柱子单调栈更顺手因为它维护的就是“下一个更高”的结构关系。如果问题只是简单的连续子数组和滑动窗口和前缀和往往更直接。双指针的本质是“在特定顺序下能证明某块搜索区间可以安全收缩”这个顺序可以是数组有序、两侧高度关系或者某种单调性。没有这种结构在背后支撑生搬双指针只会写出看不懂还跑不对的代码。最后聊点我个人的笨办法。当初学这题时我没有直接背双指针模板而是把上面那张状态表在纸上一步步画出来每次指针要移动时都问自己一句“现在结算这个位置到底凭什么安全”大概画了五六组不同的数组之后那个“矮的一侧可以放心结算”的感觉才算真正长进脑子里。后来面试再遇到这题我已经不需要回忆代码了直接从水量公式开始推顺手就写出了双指针。如果你也在准备这类题我真心建议你亲自拿纸笔画一遍状态表比把答案刷三遍都管用。
