要说算法面试里哪个题目最能检验数组功底，我第一个想到的就是接雨水。题目本身一句话就能说清：给出一列非负整数，表示每根宽度为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]验证一下：中间位置 i=1，左最高是 2，右最高是 2，min(2, 2) - 0 = 2，所以能接 2 格水。而端点 i=0，左最高是 2，右最高是 2，min(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]，算 i+1 位置时又扫了[0..i+1]，中间大量重叠区间被反复遍历。
最容易想到的优化是预处理两个数组：从左到右扫一遍记录每个位置的左侧最高，从右到左扫一遍记录每个位置的右侧最高。这样每个位置的左右最高都能在 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。
| 步骤 | left | right | 结算侧 | 当前高度 | left_max | right_max | ans |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 11 | 左 | 0 | 0 | 0 | 0 |
| 2 | 1 | 11 | 右 | 1 | 0 | 1 | 0 |
| 3 | 1 | 10 | 左 | 1 | 1 | 1 | 0 |
| 4 | 2 | 10 | 左 | 0 | 1 | 1 | 1 |
| 5 | 3 | 10 | 右 | 2 | 1 | 2 | 1 |
| 6 | 3 | 9 | 右 | 1 | 1 | 2 | 2 |
| 7 | 3 | 8 | 右 | 2 | 1 | 2 | 2 |
| 8 | 3 | 7 | 左 | 2 | 2 | 2 | 2 |
| 9 | 4 | 7 | 左 | 1 | 2 | 2 | 3 |
| 10 | 5 | 7 | 左 | 0 | 2 | 2 | 5 |
| 11 | 6 | 7 | 左 | 1 | 2 | 2 | 6 |
最后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[:i+1])在循环内求左最高 | 退化回 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 表，双指针做不到离线随机查询。如果问题需要找出每个位置左右第一个比自己高的柱子，单调栈更顺手，因为它维护的就是“下一个更高”的结构关系。如果问题只是简单的连续子数组和，滑动窗口和前缀和往往更直接。
双指针的本质是“在特定顺序下，能证明某块搜索区间可以安全收缩”，这个顺序可以是数组有序、两侧高度关系，或者某种单调性。没有这种结构在背后支撑，生搬双指针只会写出看不懂还跑不对的代码。
最后聊点我个人的笨办法。当初学这题时，我没有直接背双指针模板，而是把上面那张状态表在纸上一步步画出来，每次指针要移动时都问自己一句：“现在结算这个位置，到底凭什么安全？”大概画了五六组不同的数组之后，那个“矮的一侧可以放心结算”的感觉才算真正长进脑子里。后来面试再遇到这题，我已经不需要回忆代码了，直接从水量公式开始推，顺手就写出了双指针。如果你也在准备这类题，我真心建议你亲自拿纸笔画一遍状态表，比把答案刷三遍都管用。
