接雨水双指针解法：从暴力到最优，一次搞懂核心原理

接雨水这道题双指针是公认最漂亮的解法之一。几乎每个刷算法题的人都会在某一天撞上它它看起来像一道模拟题实际上藏着一个关于“边界”的深刻结论只要能证明矮的一边可以先结算整个问题就能压缩到一次遍历。这篇文章把双指针从暴力解法到优化版本拆开来讲包括核心原理、代码模板、手推案例以及我自己调这类题的几个习惯。适合刚接触双指针的初学者也适合想给面试讲法梳理逻辑的读者。1. 先看懂题目每个位置到底能存多少水1.1 题目的真实含义给定一个非负整数数组height每个数字代表一根宽度为 1 的柱子高度。比如[0,1,0,2,1,0,1,3,2,1,2,1]可以想象成 12 根柱子排成一排。下雨之后柱子之间的低洼处会积水题目问的是总共能接多少单位的水。我第一次做这道题时最困惑的点是“水为什么不会从两边流走”。实际上最左边和最右边的柱子外侧是没有墙的所以水只能存在“左右都被更高柱子围住”的凹陷里。中间某个位置能存多少水取决于三件事当前柱子的高度、左边所有柱子的最高值、右边所有柱子的最高值。用一个最简单的例子说明数组是[1, 0, 2]。中间 0 的位置左边最高是 1右边最高是 2两边较低的那一个是 1所以水位最高到 1减去当前位置的高度 0正好装 1 单位水。如果数组是[1, 2, 1]中间 2 的位置虽然左边最高 1、右边最高 1但 min(1,1)-2 是负数说明它是凸出来的柱子装不了水按 0 处理。所以每个位置的水量公式是water[i] max(0, min(left_max[i], right_max[i]) - height[i])其中left_max[i]是height[0..i]的最大值right_max[i]是height[i..n-1]的最大值。这里为什么必须含当前位置因为计算的是“当前这格能不能低于两边水位”如果当前位置本身就是最高点差值必然为负直接取 0 就行。这也是做这道题最重要的视角不要一上来想着整体有多少水而是把每一格的水量算清楚再累加。这个公式也被称作“木桶效应”一格子的水位由左右两边最高的墙共同决定且不会超过较矮的那一边。想通这一点后面所有解法都是围绕怎么高效求出每个位置的left_max和right_max来展开的。1.2 暴力解法的思考路径最直觉的做法是遍历每一个位置向左扫描一遍找最大值再向右扫描一遍找最大值然后套公式。代码写出来大概是这样def trap_brutal(height): n len(height) ans 0 for i in range(n): left_max 0 for j in range(i, -1, -1): left_max max(left_max, height[j]) right_max 0 for j in range(i, n): right_max max(right_max, height[j]) ans max(0, min(left_max, right_max) - height[i]) return ans这个版本的时间复杂度是 O(n^2)空间复杂度是 O(1)。虽然慢但它的正确性最容易验证。我建议初学者先把这个版本写对再去想优化。很多人在暴力版就已经踩坑了有人只找max(height[:i])而不是max(height[:i1])导致当前位置自己是最高时被错误地算成能存水也有人忘记max(0, ...)这一层保护在凸起位置减出负数把总水量算小。暴力解法的价值不只是“能跑”它还能当对拍工具。后面写双指针时如果心里没底可以随机生成几组数组拿暴力结果和双指针结果对比。这个习惯能救回很多莫名其妙的 bug。暴力解法慢在重复扫描。每个位置都要重新看一遍左右导致大量计算是重复的。于是自然想到能不能提前把每个位置的左右最大值都存下来这就引出了动态规划解法。2. 动态规划和单调栈双指针的两条“前传”2.1 动态规划空间换时间的经典方案动态规划的思路很直接用两个数组记录每个位置的左右最大值。left_max[i]表示从数组开头到位置 i 的最大高度。right_max[i]表示从位置 i 到数组结尾的最大高度。初始化时left_max[0] height[0]right_max[n-1] height[n-1]。然后从左往右更新left_max[i] max(left_max[i-1], height[i])从右往左更新right_max[i] max(right_max[i1], height[i])。得到两个数组后再扫一遍套公式求和。代码是这样def trap_dp(height): n len(height) if n 3: return 0 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 max(0, min(left_max[i], right_max[i]) - height[i]) return ans这个版本时间复杂度是 O(n)空间复杂度是 O(n)。它比暴力好了很多但还能再优化。观察公式可以发现当我们从左向右处理时left_max[i]是已知的但right_max[i]必须靠额外数组提前算好反过来从右向左处理也一样。双指针的巧妙之处就是让左右两边同时向中间走把两个数组压缩成两个变量。动态规划是理解双指针最好的跳板。双指针本质上是“一边遍历一边结算”的 DP 空间优化版只不过结算时机被精确到了指针移动的瞬间。2.2 单调栈另一种可行的思路除了动态规划还有一个常见解法是单调栈。它维护一个从栈底到栈顶递减的柱子高度当遇到一根比栈顶更高的柱子时说明栈顶位置形成了一个可以装水的凹槽。具体逻辑是当前高度height[i]大于栈顶高度时先把栈顶弹出作为凹槽底部再看新的栈顶作为左边边界如果栈不为空凹槽宽度是i - new_top - 1高度是min(height[i], height[new_top]) - bottom_height水量是宽乘高。之后继续判断直到当前柱子可以正常入栈。单调栈的时间复杂度也是 O(n)空间复杂度是 O(n)。它的优点是能处理一些需要找“左右第一个更高柱子”的题目比如最大矩形面积思路可以迁移。缺点是代码细节比双指针多稍不注意就会在“弹出后栈为空”和“宽度计算”这两个地方翻车。我在实际刷题中单调栈一般只在题目明确暗示需要“左右第一个更大元素”时才用。对于接雨水本身单调栈不是最优选择因为双指针在同样 O(n) 时间下做到了 O(1) 空间面试回答起来也更清爽。这也是为什么大家最终都把双指针当作这道题的标准答案。3. 双指针的核心原理为什么矮的一边可以先结算3.1 双指针怎么避免额外数组双指针的解法定下两个指针left从 0 往右走right从n-1往左走。同时维护两个变量left_max左边已经扫过的区域里柱子的最大高度。right_max右边已经扫过的区域里柱子的最大高度。每一轮先更新指针位置对应的最大值再比较left_max和right_max。如果left_max right_max就结算左指针位置的水量然后左指针向右移动否则结算右指针位置的水量右指针向左移动。这个框架的代码很简短left, right 0, n - 1 left_max right_max 0 ans 0 while left right: left_max max(left_max, height[left]) right_max max(right_max, height[right]) if left_max right_max: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1这里有一个关键细节结算时不需要max(0, ...)因为left_max在更新时已经包含了height[left]所以left_max - height[left]一定不小于 0右边同理。有人可能会问right_max不一定是整个右侧的最大值因为中间还有未扫描的区域凭什么用它来决定左指针位置的水量这正是双指针正确性最值得深挖的地方。3.2 正确性论证一次遍历为什么不漏算我们把指针状态拆开看。当指针停在left和right时意味着left左侧的所有柱子都已经扫描过所以left_max就是数组在[0..left]范围内的完整最大值。right右侧的所有柱子都已经扫描过所以right_max就是数组在[right..n-1]范围内的完整最大值。尚未扫描的区域是(left, right)这一小段中间地带。现在看left_max right_max的情况。左侧完整最大值是left_max右侧完整最大值虽然还不知道但它至少是right_max。因为right_max left_max所以右侧整体最大值一定大于左侧完整最大值。位置left真正需要的水位是min(左侧整体最大, 右侧整体最大)而右侧一定比left_max高所以这个最小值就是left_max。于是left位置的水量可以放心地用left_max - height[left]结算和中间未扫描区域有没有更高的柱子完全无关。反过来当left_max right_max时左侧完整最大值至少是left_max右侧完整最大值就是right_max。因为左边已经确定能盖过right_max位置right的水位由right_max决定所以结算right_max - height[right]也是安全的。这个论证的核心是每次结算的那一侧它的完整边界最大值是已知的另一侧只需要提供一个“足够的支撑高度”不需要完整信息。因为水的瓶颈永远在较矮的那一边而较矮的一边恰好是我们已经掌握了全部信息的那一边。我最初学双指针时一直纠结“右边没扫完怎么办”。后来用[5,0,3]这个例子手推了一遍才明白先更新right_max3因为left_max5 3于是结算右边位置的水量 3-03一步到位根本不需要知道左边中间还有没有更高的柱子。这就是双指针的数学美感它不是模拟水流而是在每一步都锁定了一个确定性的水位线。3.3 两种常见写法的差别我在网上看到过两种双指针写法。一种就是上面这种“先更新最大值再比较”的版本另一种是先比较height[left]和height[right]的大小然后移动较矮的一侧。第二种写法长这样while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: ans left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: ans right_max - height[right] right - 1它也能正确运行思路是“矮的一边先结算”。但面试时我推荐第一种“先更新再比较”的写法因为它和动态规划的公式长得更接近讲解时可以直接复用min(left_max, right_max)的概念听的人更容易跟上来。第一种写法里比较的对象是left_max和right_max而不是height[left]和height[right]。这一点很容易被误解成“比较当前柱子的高度”我曾经就吃过这个亏。如果写成了if height[left] height[right]再配合先更新最大值某些数据下会算错因为当前柱子的高矮并不代表两侧最高峰的高矮。4. 手把手代码实现从模板到完整推演4.1 标准代码模板把前面的代码整理成完整函数def trap(height): n len(height) if n 3: return 0 left, right 0, n - 1 left_max, right_max 0, 0 ans 0 while left right: left_max max(left_max, height[left]) right_max max(right_max, height[right]) if left_max right_max: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans提前判断n 3并不是必须的因为就算不判断循环也会自动处理但加上之后逻辑更清晰少于三根柱子无论如何都不可能有积水。这个判断也避免了某些边界测试用例里不必要的计算。代码中还有一个值得注意的点左右最大值初始化为 0。题目假设柱子高度非负所以 0 是安全初值。如果输入的数组可能包含负数这个初始化就不成立了但常规算法题不会有这种设定。4.2 经典案例逐步推演用经典数组[0,1,0,2,1,0,1,3,2,1,2,1]完整走一遍。初始化left0right11left_max0right_max0ans0。每一步先更新左右最大值再决定移动方向。完整过程如下步骤leftrightleft_maxright_max比较结果结算水量累计水量101101left_max right_max00211111left_max right_max00311012left_max right_max00421012left_max right_max11531022left_max right_max0163922left_max right_max1273822left_max right_max0283723left_max right_max0294723left_max right_max13105723left_max right_max25116723left_max right_max16最终答案是 6。这个数组是接雨水题目里最经典的用例很多讲解都会拿它举例。如果你能把这 11 步在纸上自己推一遍双指针的理解基本就到位了。推演时最值得关注的是第 8 步到第 11 步。此时left进入了一块两边都比较高的低洼区left_max停在 2right_max被右边的 3 顶住所以中间连续三个位置都按照2 - height[i]结算。这就是双指针的“批量结算”能力一旦两边边界最大值确定中间洼地就是按同一个水位算的。4.3 边界条件与特殊场景除了经典用例我建议多测几类边界数据它们往往能暴露出写法上的问题。第一类是长度小于 3 的情况比如[]、[1]、[1,2]。这些数据答案都是 0。代码里的提前判断已经把这种情况挡住了。第二类是递增或递减序列比如[1,2,3,4]和[4,3,2,1]。这种地形没有洼地答案应该是 0。用双指针跑一下会发现它不断移动较高的那一边但水量永远加 0最后正常返回 0。第三类是完全相同的柱子比如[2,2,2,2]。答案也是 0。这里要注意的是比较分支用left_max right_max还是。如果用相等时走 else 结算右边结果正确如果用相等时结算左边结果同样正确。只要保证“每次只移动一个指针且不重复结算相遇位置”就不会出问题。第四类是最高峰在中间的情况比如[1,2,1,3,1,2,1]。这种数据最能检验代码是否会把最高峰两侧的水量算错。手推之后会发现最高峰位置最终成了左右指针的分界线左右两侧分别由各自的边界最大值结算互不干扰。还有一个容易忽略的点在 Python 里整数不会溢出但在 C/Java 里极端数组累加的水量可能超过 32 位整数范围需要把答案变量声明为long或long long。虽然常规测试用例不会这么夸张但养成这个习惯能避免线上环境的数据类型问题。5. 复杂度分析为什么双指针是面试性价比之王5.1 时间和空间复杂度拆解双指针版本只遍历数组一次left和right各自最多移动一个数组长度所以总移动次数是 O(n)。每一步只做常数次比较、加减法和最大值更新因此时间复杂度是 O(n)。空间上只用了四个变量left、right、left_max、right_max。这四个变量不随输入规模增长所以空间复杂度是 O(1)。对比动态规划版本DP 需要两个长度为 n 的辅助数组空间 O(n)。双指针用“边结算边丢弃”的方式省掉了这两个数组这是它最大的优势。有时候面试官会追问能不能证明它一定不会漏算这时候把上一节的正确性论证讲一遍就够了。重点突出两点一是每次结算低水位一侧时另一侧的高度已经足够兜底二是未扫描区域的高度只会让结果更倾斜于已经确定的边界不会把已结算水位抬高。5.2 四种方法怎么选把暴力、动态规划、单调栈、双指针放在一起对比解法时间复杂度空间复杂度核心思路适合场景暴力O(n^2)O(1)每个位置重新找左右最大用来验证正确性、对拍动态规划O(n)O(n)预处理左右最大值数组适合讲解递推公式单调栈O(n)O(n)维护递减栈按层算水可迁移到最大矩形等题双指针O(n)O(1)从两边逼近矮边结算面试标准答案、竞赛常用我的实际选择是日常练习时先写 DP因为它最接近题目公式思路不容易走偏追求最优解时写双指针只有遇到“找左右第一个更高柱子”的题干时才考虑单调栈。双指针也不总是最优。某些变形题需要输出每个位置的实际水量或者需要知道每个凹槽的左右边界这时候 DP 的辅助数组反而更好用。选方法不能只看复杂度还要看题目想要什么信息。6. 调试技巧与刷题心得6.1 自己写的双指针为什么总多水这个代码短但错误率不低。我见过最多的错误是“更新最大值的时机错了”。有人习惯先把当前水量算了再更新最大值。对双指针来说这是致命的。因为结算用的是当前指针位置已经纳入的最大值如果漏了当前位置遇到[5,0,3]这种数据第一次结算就会把左边界 5 当成左最大多算 5 单位水。先更新再结算顺序不能颠倒。另一个常见错误是循环条件写成while left right。如果配合先更新最大值最后相遇时会多结算一次左右指针指向同一个位置left_max和right_max可能不同结算一个根本不存在的“边界水”出来。接雨水问题里相遇位置要么是最左要么是最右本来就不可能存水所以left right才是正确的循环边界。还有一种错误不太容易发现数组里有高度相同的大峰值时用height[left] height[right]的写法可能会在相等时选错移动方向。虽然“先更新最大值”版本没有这个问题但如果你读代码时发现别人用了那种写法不要急着改先画几组数据验证两种写法在一定条件下是等价的但混着用才会出事。6.2 两个实用的小技巧第一个技巧是暴力对拍。写双指针之前先写一个暴力版本然后用随机数组批量比对。我通常生成 1000 组长度 1 到 20 的随机数组比较两个函数输出是否一致。只要有一组不一致就把数组打印出来手动走一遍。这个流程能覆盖绝大多数边界情况比肉眼 debug 高效得多。第二个技巧是可视化推演。遇到卡壳时不要只看代码把数组画成柱状图在图上标出左右指针位置和两个最大值。很多问题一眼就能看出来比如“这个位置为什么结算成 0”很可能是因为left_max刚好等于当前高度而不是真的没有边界。我个人刷这类题还有一个习惯每写完一种解法就在注释里写一句话总结它的核心思想。暴力是“重复扫描”DP 是“空间换时间”单调栈是“找最近更高柱子”双指针是“边遍历边结算”。等一个月后再回头看这些注释会比直接看代码更快回忆起整个思路。接雨水的双指针解法代码量很小但背后牵扯出来的东西很多。它串联起了暴力、动态规划、单调栈、双指针这四条典型路线也算是一道能检验基础功的题目。如果你正在准备面试建议把这四种解法都亲手敲一遍再用双指针作为最终答案。能把为什么“矮边先结算”讲明白这道题才算真正过关。