接雨水这道题，双指针是公认最漂亮的解法之一。几乎每个刷算法题的人都会在某一天撞上它；它看起来像一道模拟题，实际上藏着一个关于“边界”的深刻结论：只要能证明矮的一边可以先结算，整个问题就能压缩到一次遍历。这篇文章把双指针从暴力解法到优化版本拆开来讲，包括核心原理、代码模板、手推案例，以及我自己调这类题的几个习惯。适合刚接触双指针的初学者，也适合想给面试讲法梳理逻辑的读者。
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[:i+1])，导致当前位置自己是最高时被错误地算成能存水；也有人忘记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[i+1], 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_max=3，因为left_max=5 > 3，于是结算右边位置的水量 3-0=3，一步到位，根本不需要知道左边中间还有没有更高的柱子。这就是双指针的数学美感：它不是模拟水流，而是在每一步都锁定了一个确定性的水位线。
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]完整走一遍。初始化left=0，right=11，left_max=0，right_max=0，ans=0。
每一步先更新左右最大值，再决定移动方向。完整过程如下：
| 步骤 | left | right | left_max | right_max | 比较结果 | 结算水量 | 累计水量 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 11 | 0 | 1 | left_max < right_max | 0 | 0 |
| 2 | 1 | 11 | 1 | 1 | left_max >= right_max | 0 | 0 |
| 3 | 1 | 10 | 1 | 2 | left_max < right_max | 0 | 0 |
| 4 | 2 | 10 | 1 | 2 | left_max < right_max | 1 | 1 |
| 5 | 3 | 10 | 2 | 2 | left_max >= right_max | 0 | 1 |
| 6 | 3 | 9 | 2 | 2 | left_max >= right_max | 1 | 2 |
| 7 | 3 | 8 | 2 | 2 | left_max >= right_max | 0 | 2 |
| 8 | 3 | 7 | 2 | 3 | left_max < right_max | 0 | 2 |
| 9 | 4 | 7 | 2 | 3 | left_max < right_max | 1 | 3 |
| 10 | 5 | 7 | 2 | 3 | left_max < right_max | 2 | 5 |
| 11 | 6 | 7 | 2 | 3 | left_max < right_max | 1 | 6 |
最终答案是 6。这个数组是接雨水题目里最经典的用例，很多讲解都会拿它举例。如果你能把这 11 步在纸上自己推一遍，双指针的理解基本就到位了。
推演时最值得关注的是第 8 步到第 11 步。此时left进入了一块两边都比较高的低洼区，left_max停在 2，right_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 是“空间换时间”，单调栈是“找最近更高柱子”，双指针是“边遍历边结算”。等一个月后再回头看这些注释，会比直接看代码更快回忆起整个思路。
接雨水的双指针解法，代码量很小，但背后牵扯出来的东西很多。它串联起了暴力、动态规划、单调栈、双指针这四条典型路线，也算是一道能检验基础功的题目。如果你正在准备面试，建议把这四种解法都亲手敲一遍，再用双指针作为最终答案。能把为什么“矮边先结算”讲明白，这道题才算真正过关。
