我第一次认真做接雨水这道题时刚被双指针连续按在地上摩擦过。当时看了一眼题目描述觉得有戏——把每个位置左右两边的最高墙找出来取矮的那根减去当前位置高度累加一下不就是答案吗暴力写完提交一个超时提示直接把我拉回现实。后来把这道题彻底摊开研究才发现它最妙的地方不在能解出来而在于一个小观察如何把 O(n²) 的暴力砍成 O(n)顺带把空间压到 O(1)。这篇文章就围绕双指针解接雨水这个经典问题从暴力直觉讲到边界细节再到同类题迁移适合正在刷算法题、准备面试、或者想把双指针真正吃透的读者。1. 第一眼看到接雨水从暴力直觉到瓶颈暴露1.1 题目本质每个凹槽的存水量公式先看题目到底在问什么。给定 n 个非负整数 height每个数字代表一根宽度为 1 的柱子的高度把这些柱子立起来之后下雨问总共能接住多少单位的雨水。高度图长什么样不重要重要的是每个位置能存多少水。雨水只会积在柱子之间的低洼处。对任意一个位置 i它能存的水不取决于左边哪面墙最高也不取决于右边哪面墙最高而是取决于两侧最高墙中较矮的那一根。公式就是位置 i 的存水量 min(max_left[i], max_right[i]) - height[i]如果这个值是负数则记为 0。这个公式可以拿生活场景类比两排楼之间的地面凹坑能积水的高度永远被矮的那一侧决定。只要有一侧的挡水墙不够高水就会从矮侧流出去凹坑再深也存不住。所以短板效应在这里是字面意义上的。举个例子height [0, 1, 0, 2]。位置 2 高度为 0它左边的最高墙是 1右边的最高墙是 2min 是 1所以能接 1 单位水。而位置 3 是右边界它的 max_right 为 0接水量直接算成负数取 0。边界位置天然存不了水这个公式会自动处理。1.2 暴力解法为什么必然超时最直觉的做法就是针对每个 i往左扫一遍找 max_left往右扫一遍找 max_right套公式累加。代码很短思路也通顺但复杂度是 O(n²)。为什么超时假设数组长度 n 20000最坏情况下要执行约 4 亿次比较操作在线刷题平台的时限通常在 1 到 2 秒4 亿次是铁定跑不完的。更本质的问题是这里面存在大量重复计算。位置 i 的 max_left 和位置 i1 的 max_left 其实高度相关可暴力算法每次都从头扫一点都没复用。如果意识到这一点很自然会想到预处理先从左到右扫一遍算出每个位置的左侧最大值数组再从右到左扫一遍算出右侧最大值数组。这样每个位置 O(1) 就能拿到 min 值总复杂度 O(n)空间占用 O(n)。这个版本已经能通过评测了但面试官大概率会追问一句能不能把空间也优化掉于是双指针就该登场了。2. 双指针为什么能出现从两端向内收缩的关键洞察2.1 矮的那一侧决定了当前格子的人生双指针解法的核心洞察一句话就能概括当 height[left] height[right] 时left 位置能接多少水只由 left_max 决定跟 right 到 left 之间那一片未知区域无关。这句话值得反复琢磨。假设 left 指针站在一根高度为 2 的柱子上right 指针站在高度为 7 的柱子上左侧扫过的历史最高墙是 3。对当前 left 位置来说右侧最高墙至少是 7哪怕 left 和 right 中间全是平地右侧那根 7 也足够当右挡板。根据取较小的逻辑min(left_max, right_max) 里右侧完全不会拖后腿所以当前格子水位只由 left_max 决定。就算中间还有一根更高的柱子右边界只会变得更高但 min 里用的是矮的那根右侧再高也不影响结论。这个观察的本质是左右两根指针像两堵墙从两侧向内逼近哪边矮哪边的位置就先定稿。高的一侧还在为中间那些未知凹槽留着可能性。2.2 双指针的决策规则谁矮谁动维护两个变量 left_max 和 right_max分别表示当前左指针左侧含左指针的最高墙、右指针右侧含右指针的最高墙。每轮循环做一次比较如果 height[left] height[right]说明左侧是更矮的挡板左指针所在位置的水量已经由 left_max 锁定。更新 left_max累加当前格子的水量然后 left 向右移动一格。否则对称处理右侧更新 right_max累加水量right 向左移动一格。为什么移动的是矮侧因为矮侧是当前瓶颈。当前格子的水量由短板决定而短板这一侧的最高墙已经被历史最大值完整刻画了信息已经足够再留着这根矮柱子也没有意义——它不是任何后续位置的有效右边界。移动它去探索还没定稿的区域是唯一不会丢信息的选择。2.3 为什么不会漏掉中间的凹槽很多人第一次看双指针解法会犯嘀咕只扫一遍凭什么不会漏掉中间那些凹槽道理在于每个位置的水量一定是在它被指针扫过的那一瞬间被永久确定的之后不会再被访问。left 向右移动时它经过的所有位置都处于右侧至少有一根 height[right] 的墙托底这个安全语境下所以它们的右边界信息不需要依赖右侧尚未探索的细节。right 向左移动时完全对称。中间那些真正存水的凹槽会在指针恰好经过它们时被正确计算。这不是碰运气而是一个严格成立的归纳过程每次移动前当前指针位置的条件都已经满足了计算要求。这一步想透了双指针的 O(n) 时间、O(1) 空间也就说得通了。它本质上是用矮侧信息已完备这个逻辑省掉了一整套预处理数组。3. 手撕双指针代码从循环到每一步水量累加3.1 可以直接跑的代码先给一份 Python 版本短而且好读def trap(height): if not height: return 0 left, right 0, len(height) - 1 left_max, right_max height[left], height[right] 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再用 C 写一版方便面试手写时参考class Solution { public: int trap(vectorint height) { if (height.empty()) return 0; int left 0, right height.size() - 1; int left_max height[left], right_max height[right]; long long ans 0; while (left right) { if (height[left] height[right]) { left_max max(left_max, height[left]); ans left_max - height[left]; left; } else { right_max max(right_max, height[right]); ans right_max - height[right]; --right; } } return ans; } };代码有一个细节值得注意进入分支后先更新对应的 max再累加水量。原因是当前柱子本身也可能成为后续格子的历史最高墙所以要先让它进入 max 的候选集合同时 max 更新后再相减能保证结果一定非负。这个顺序在下一章会展开讲。3.2 用 [0,1,0,2,1,0,1,3,2,1,2,1] 完整走一遍网上最经典的测试用例就是这一组答案是 6。我手动跟踪一遍每轮循环的状态都列出来轮次leftright分支判断left_maxright_max本轮水量累计 ans初始011-01-010110 1 走左010021111 1 走右010031101 2 走左110042100 2 走左111153102 2 走右12016392 1 走右12127382 2 走右12028372 3 走左22029471 3 走左221310570 3 走左222511671 3 走左2216从表里能看出一个规律前几轮虽然指针在动但累加的水量一直是 0直到 left 移到 index 2 才开始真正接水。这是因为左侧的历史最高墙从 0 升到 1而 index 2 的地面高度是 0于是一下子能存 1 单位水。到第 8 轮left 碰到高度 2 的柱子left_max 从 1 跳到 2为后面 index 4、5、6 三个凹槽的蓄水提供了左侧挡板。整个过程中 right 侧也贡献了两次水量分别在 index 9 和 index 8 附近。答案是 6和题目一致。3.3 边界条件速查输入特征期望结果原因空数组0没有柱子自然没水只有一个元素0形不成凹槽单调递增如 [1,2,3,4]0水全往右流走单调递减如 [4,3,2,1]0水全往左流走等高平台如 [5,5,5]0没有低洼处[3,0,3]3中间凹槽两侧等高单调递增或递减为什么是 0因为整个图形是斜坡雨水落到坡面上会顺着流走没有任何左右双高夹一低的凹形结构。等高平台同理。双指针代码处理这些 case 都很自然唯一的共同点是循环正常结束ans 不增长。4. 踩坑实录双指针解法最容易翻车的地方4.1 边界等号height[left] 等于 height[right] 时走哪边很多人会纠结if height[left] height[right]用的是严格小于那么相等时走了 else 分支它会移动 right 而不是 left。这样安全吗安全。假设两侧柱子一样高此时无论把哪一侧作为当前已定稿的位置计算出的水量都不会出错。可以这样理解当 height[left] height[right] 时两侧墙的高度相同当前指针位置的水量要么是 0要么已经能由自己这一侧的 max 完全确定。比如 left_max 和 right_max 都是 5height[left] height[right] 5那左右两边各自算出的水量都是 5 - 5 0结果完全一样。如果你看别人的代码有人写有人写其实都对。真正需要注意的是选定一种写法后要保持一致不要一会儿走左一会儿走右那样跟踪状态会把自己绕晕。我习惯写相等时默认走右侧处理原因是这样可以少一次不确定的分支判断逻辑更清爽。4.2 更新 max 与计算水量的顺序不能反过来我见过不少版本把代码写成这样ans min(left_max, right_max) - height[left] left_max max(left_max, height[left])这种先算后更新的写法在某些 case 里会算出负数。找一个具体例子height [4, 2, 0, 3]。初始化 left_max 4right_max 3。如果第一轮走的是 right 分支先执行ans min(4, 3) - height[right]也就是 3 - 3 0看起来没毛病但如果先执行的是 left 分支min(4, 3) - height[left] 3 - 4 -1这就错了。这个坑的本质是对于某一侧的最高墙本身就出现在当前指针位置的情况必须先让当前柱子归入历史最大值再去算它头顶能存多少水。否则你会拿还没有包含当前柱子的旧 max 去减当前高度一旦当前柱子恰好是历史最高结果就变成负的。正确顺序一定是先left_max max(left_max, height[left])再ans left_max - height[left]。同理right_max也要先更新。4.3 int 溢出与数据范围很多题解都用int存答案在常见数据范围内没问题但如果你遇到变种题height 长度拉到 2×10^4height[i] 拉到 10^5极端情况下比如 [100000, 0, 100000, 0, 100000, ...] 这种间隔凹槽总水量可以逼近 10^9已经非常接近 32 位 int 的上限 2.147×10^9。再激进一点的数据范围int 就装不下了。所以 C 版本里我用的是long long。面试时主动提一句这里用 long long 是为了防止极端数据溢出是很加分的细节。Python 不必担心整数是任意精度的。另外还要注意左右指针的类型如果用size_t循环结束时 right 不会减成负数因为循环条件保证了 left right 时 right 至少为 1这个可以放心。4.4 一个隐蔽 bug初始 max 到底取多少有人把 left_max 和 right_max 初始化为 0然后进入循环先更新再计算结果其实也对。但有一个版本容易出问题初始化时先单独把左右端点的水量算一遍再进入 while 循环。比如left_max, right_max 0, 0 while left right: # 这里如果边界位置先算一遍后续会有重复计算这种写法既啰嗦又容易重复累加边界的水量。最干净的做法就是代码里的方案left_max 和 right_max 直接取首尾柱子的高度然后立即进入循环。因为首尾柱子作为边界它们的头顶本就不可能有水而且它们会成为后续内部位置的历史挡板必须先进入 max。初始化成首尾高度正好满足这个需求。5. 思路迁移接雨水之外的双指针5.1 盛最多水的容器同源同构的双指针接雨水有一个著名的近亲盛最多水的容器。问题描述是给定一组隔板高度选两个隔板装水问最大面积是多少。它也用双指针从两端向中间收缩每次移动矮的那一侧。对比一下两者的异同对比项接雨水盛最多水的容器状态维护需要维护 left_max 和 right_max不需要历史 max直接用当前两根柱子的高度计算对象每个单柱头顶的存水量全部累加两个柱子的围合面积取最大值指针移动依据矮侧指针移动矮侧指针移动结束条件left rightleft right共同的内核是矮的那一侧决定了当前的上限因此它可以被安全舍去。不同之处在于接雨水要的是每个格子的累加水量所以必须不断维护历史最高墙容器题要的是全局最大面积所以每一轮都用当前的min(height[left], height[right]) * 宽度跟答案比大小不需要任何历史状态。5.2 双指针失效的预警信号不是所有两端收缩问题都能用双指针。判断标准其实就一条移动某一侧之后是否能保证被永久排除的那些解不可能成为最优解。接雨水成立因为矮墙决定了右侧或左侧的水位上限移走它不会丢掉任何更优的蓄水组合。如果问题要求必须同时知道两侧的内部结构才能做决策那双指针就会失效。举个例子接雨水原题每根柱子宽度是 1如果你把变种改成每根柱子宽度各不相同双指针的推导基础就不成立了这时通常要换单调栈思路——从左到右维护一个单调递减栈遇到更高的柱子就弹出栈顶并计算凹槽水量。单调栈解法同样是 O(n)但空间是 O(n)需要额外维护栈。它比双指针更通用但代码也更绕。我的建议是双指针能解决的就别上单调栈除非明确需要输出每个凹槽的位置信息那时候单调栈反而直观。5.3 刷这类题目先回答三个问题把接雨水的思路想透之后我总结了一套判断双指针适用性的方法遇到新题时先问自己三个问题问题一结果是由两侧极值决定的还是由局部相邻关系决定的前者更可能用双指针后者往往要栈、差分或排序。问题二移动矮侧之后会不会存在一个更优解恰好以这根矮柱子为边界如果存在就不能移动如果不存在就可以放心移动。接雨水的正确性就建立在矮柱子不可能是更优边界上。问题三需要维护的状态是历史极值还是当前位置的值像接雨水需要历史极值就要额外维护两个 max像容器题只需要当前值就用不到。这三个问题答完能不能用双指针、怎么写基本上就不会犹豫了。刷了这么多双指针题我个人觉得接雨水是其中最值得反复琢磨的一道。它把为什么可以省掉一次扫描这个核心矛盾展示得特别清楚你一旦想明白矮侧决定上限这件事很多看似玄乎的双指针题目都会变得朴素起来。我的习惯是不管在哪个题库里遇到它都先自己写一遍暴力再想一遍预处理优化最后用双指针收尾。这个流程比直接背题解有用得多至少下次面试被问到你能从我理解这个问题的瓶颈在哪开始讲而不是上来就背代码。如果这篇文章能让你下次碰见双指针题时第一反应是问自己矮的这一边是不是说了不算那这通篇就没白写。