LeetCode 42题，接雨水。如果你刷过几轮算法题，几乎不可能没遇见过它。我自己的感受是，这道题在算法题单里的地位高得吓人，很多面经都把它挂在高频榜上。它不像动态规划有那么曲折的状态定义，也不像图论需要大量前置知识，但它恰好覆盖了暴力枚举、动态规划、双指针、单调栈这四种最核心的解题范式。很多人看完答案觉得自己懂了，换一道变形题又懵了，原因往往在于只看懂了某一版代码，但没有把从“暴力”到“最优解”的完整思考链吃透。这篇文章我会沿着我在实际刷题和带新人时反复验证过的一条路线，把这道题拆干净，每一步都会解释为什么这么做，同时把我踩过的坑、调试时总结的经验一并放进来。适合所有准备算法面试、或者想系统地过一遍双指针和单调栈这两种高频技巧的人。
1. 题目到底在问什么：把“接水”翻译成数学表达式
1.1 雨水的形成条件：为什么必须是“两边高中间低”
先花30秒想一个生活场景。下雨之后，水为什么能积在某些地方？因为那个位置本身低，而且左右两边都有更高的东西挡住。对于一排宽度为1的柱子来说，某个位置要想留住雨水，左侧得有一根比它高的柱子，右侧也得有一根比它高的柱子。注意，这里说的是“有一根”，不要求相邻。很多初学者第一步就想歪了，总盯着相邻柱子找凹槽，比如看到 [2,1,2] 知道中间能存水，但遇到 [3,0,2,1,4] 这种跨度很大的凹陷就反应不过来了。根因在于，水是液体，是平的，它可以在多根柱子上方铺开，只要左右两侧各有一堵更高的墙，中间整片低洼区域都能蓄水。
所以正确的思考单位不是“相邻的两个柱子”，而是“某个位置左侧所有柱子的最高值”和“右侧所有柱子的最高值”。对位置 i 来说，它头顶能留存的水量，取决于它左边所有柱子的最大高度，记作 leftMax，以及它右边所有柱子的最大高度，记作 rightMax。水会从两侧中较矮的那一侧流走，所以最终水位被两侧较矮的那一边决定。这个道理和木桶原理完全一样：一只木桶能装多少水，取决于最短的那块板。于是，位置 i 能够接到的水量就是 min(leftMax, rightMax) - height[i]，如果这个差值是负数，说明当前位置本身已经高过了两侧能围起来的水位，那就不积水，按0算。
1.2 用一个具体例子建立直觉
经典测试用例 height = [0,1,0,2,1,0,1,3,2,1,2,1]，标准答案是6。你暂时不需要关心怎么计算，只用手比划一下柱状图：最高的柱子高度是3，整个图里凡是低于左右两侧高墙的凹陷位置，都可能有水。最左边高度0的那根柱子，以及最右边高度1的柱子，都在边界上，边界外侧没有墙，水直接流走，不可能积水。真正能蓄水的，是中间那些被两侧高柱围住的低洼格子。数一数这些格子，一共6个。看答案之前，我强烈建议你在纸上把这个柱状图画出来，然后像玩拼图一样把水填进去。这比直接看代码更符合大脑处理几何问题的直觉。
1.3 这道题真正在考你什么
公式一出来，问题就变了：不是“怎么求每个位置的水量”，而是“如何高效地拿到每个位置的 leftMax 和 rightMax”。如果对每个位置都往左往右扫描一遍，当然能拿得到，但代价是 O(n²)。能不能一趟扫描就更新出答案？能不能用常数空间？能不能换一种数格子的方式？面试官层层追问的脉络就藏在这里。接下来的内容，就是沿着这条线一步步往前走：从暴力扫描，到前后缀数组，再到双指针，最后是单调栈视角。每一步都有它存在的必要，也都对应一个面试中常见的追问节点。
2. 从暴力到动态规划：两种最直观的解法
2.1 暴力法：每根柱子单独算
暴力解法严格照着公式写即可。对每个位置 i，分别向左扫描到开头、向右扫描到结尾，求出两边的最大值，然后代入公式累计。
def trap_brute_force(height): n = len(height) if n < 3: return 0 ans = 0 for i in range(1, n - 1): 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²)，空间复杂度 O(1)。这里需要注意，扫描范围是从 i 到边缘，而不是从 i+1 或 i-1 开始，因为 leftMax 和 rightMax 必须包含 height[i] 本身，后面的优化解法能省略 max(0, ...) 也是靠这个保证的。暴力法正确性没毛病，但面试时如果直接交这版，八成会被追问“能不能更快”。它最大的问题是重复计算：每次求左边最大值，都把之前扫描过的区域重新扫了一遍，没有把已经算出来的信息保存下来。
2.2 前缀后缀最大值数组：空间换时间的标准操作
聪明的优化方式就是提前把所有位置的 leftMax 和 rightMax 存进数组。我们专门开一趟从左往右的扫描：leftMax[i] = max(leftMax[i-1], height[i])。这就把之前算过的信息全部保留下来了。再从右往左扫一趟得到 rightMax[i]。最后每个位置只需要查两个数组，O(1) 就能算出水量。
def trap_dp(height): n = len(height) if n < 3: return 0 left_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 = [0] * n 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(1, n - 1): ans += min(left_max[i], right_max[i]) - height[i] return ans时间复杂度 O(n)，空间复杂度 O(n)。这其实就是动态规划里最基础的“用表记录子问题答案，避免重复计算”的思想，只不过状态转移非常简单，一条递推式就完事。注意累计答案那一步已经不需要 max(0, ...) 了，因为 leftMax[i] 和 rightMax[i] 都至少等于 height[i]，min 之后也一定不小于 height[i]，差值不可能为负。这个细节虽然小，但能让你写的代码更干净，也说明你真的理解了这个公式的边界条件。
2.3 为什么这个解法是“舒适区”
如果面试里时间紧张，前后缀数组版本是稳妥的保底答案，逻辑直白、不容易写错、三趟扫描解释起来也快。我自己面试别人的时候，候选人能在一分钟内想出这个思路并写清楚，算法基础基本是过关的。但面试官基本不会就此打住，大概率会追问：“这个解法用了 O(n) 的额外空间，能不能把它省掉？”两个数组看起来存了所有位置的边界最大值，但仔细想一下，我们在结算答案的时候，其实并不需要一次性知道所有位置的左右最大值，只需要在当前移动到的那个位置做判断。这个观察，就指向了双指针解法。
3. 双指针解法：一趟遍历拿下 O(1) 空间
3.1 为什么可以省掉数组：只有短板决定水位
双指针不是玄学，它有一个非常硬核的正确性依据。想象我们维护两个指针 left 和 right，一左一右向中间靠拢。同时维护两个变量：leftMax 表示从最左端到 left 位置这些柱子的最大值，rightMax 表示从最右端到 right 位置这些柱子的最大值。关键推理来了：
如果 leftMax < rightMax，那么对于位置 left 来说，它左侧的最大值已经确定是 leftMax，不会再变了。右侧的最大值我们虽然还没有扫描完整，但至少已经达到了 rightMax，而且只会更高。所以 min(左侧全局最大, 右侧全局最大) = min(leftMax, 右侧最终最大) = leftMax。也就是说，位置 left 最终能存多少水，现在就彻底确定了，不必等右边扫描完。
反过来，如果 rightMax < leftMax，那么位置 right 的水量现在就确定了，等于 rightMax - height[right]。如果两者相等，结算哪一边都可以，结果完全相同。这就是“谁矮结算谁”这个口诀的来源，本质上是“短板决定水位”的直接应用。
3.2 移动与结算规则
具体做法是：初始化 left = 0，right = n-1，leftMax = 0，rightMax = 0，ans = 0。循环条件用 while left < right，每次循环先更新两个最大值，再做比较：
def trap_two_pointer(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关于左右最大值相等时走哪个分支，完全不影响正确性，我习惯用<时走左分支，相等时走右分支，只是为了代码上不出现空分支。要注意的是，因为循环开头已经先更新了 leftMax，所以它在结算时一定不小于 height[left]，rightMax 同理，因此 ans 累加的值天然非负，不需要再套 max(0, ...)。这种“先更新再结算”的写法是我强烈推荐的，理由很简单：不容易漏算，也不会算出负数，新手照着写基本不会翻车。
3.3 手动走查：看看答案是怎么一笔一笔累加出来的
纸上谈兵没有用，我们直接把经典输入 [0,1,0,2,1,0,1,3,2,1,2,1] 完整走一遍，n=12。初始 left=0，right=11，leftMax=0，rightMax=0，ans=0。
轮1：更新 leftMax=max(0,0)=0，rightMax=max(0,1)=1。0<1，结算左侧：0-0=0，left=1，ans=0。 轮2：更新 leftMax=max(0,1)=1，rightMax=1。1<1不成立，结算右侧：1-1=0，right=10，ans=0。 轮3：更新 leftMax=1，rightMax=max(1,2)=2。1<2，结算左侧：1-1=0，left=2，ans=0。 轮4：更新 leftMax=max(1,0)=1，rightMax=2。1<2，结算左侧：1-0=1，left=3，ans=1。 轮5：更新 leftMax=max(1,2)=2，rightMax=2。2<2不成立，结算右侧：2-2=0，right=9，ans=1。 轮6：更新 leftMax=2，rightMax=max(2,1)=2。2<2不成立，结算右侧：2-1=1，right=8，ans=2。 轮7：更新 leftMax=2，rightMax=max(2,2)=2。2<2不成立，结算右侧：2-2=0，right=7，ans=2。 轮8：更新 leftMax=2，rightMax=max(2,3)=3。2<3，结算左侧：2-2=0，left=4，ans=2。 轮9：更新 leftMax=max(2,1)=2，rightMax=3。2<3，结算左侧：2-1=1，left=5，ans=3。 轮10：更新 leftMax=max(2,0)=2，rightMax=3。2<3，结算左侧：2-0=2，left=6，ans=5。 轮11：更新 leftMax=max(2,1)=2，rightMax=3。2<3，结算左侧：2-1=1，left=7，ans=6。
此时 left=7，right=7，循环结束，ans=6。你看，10号位和11号位的两格水是先通过右侧指针结算的，而1号位到8号位的四格水是后面通过左侧指针结算的。我把这11轮完整列出来，是因为网上很多题解都只给个思路就跳到代码，真正动手模拟一遍之后，你才会明白为什么 ans 会在某个时刻突然加上2、加上3，而不是简单地把答案背下来。
4. 单调栈解法：一层一层数雨水
4.1 换一种计数方式：从逐列变成逐块
如果说双指针是“逐列”数水，单调栈就是“逐块”数水。你可以把柱子高度图想象成由许多小方格组成的棋盘，接雨水的总数等于所有被高墙围住的方格数。逐列法是一列一列数，单调栈则是一次性数一整块横向的水。它不再纠结于每个位置左右的最大值，而是专门处理“左高、中间低洼、现在又遇到右高”这种结构。
单调栈这个结构在题目里的典型长这样：维护一个栈，从栈底到栈顶，柱子高度是递减的。为什么要递减？因为只要高度持续下降，意味着左边没有比当前柱子更高的墙，水根本留不住。一旦遇到一个比栈顶更高的柱子，说明出现了右边界，栈里可能藏着之前留下的凹槽，需要触发结算。这就是“遇到更高柱子才干活”的设计逻辑。
4.2 弹出、结算、入栈：三步走
直接看实现，栈里存的是下标，不是高度，因为结算宽度的运算依赖下标差。
def trap_monotonic_stack(height): n = len(height) if n < 3: return 0 stack = [] ans = 0 for i in range(n): while stack and height[i] > height[stack[-1]]: bottom = stack.pop() if not stack: break left = stack[-1] width = i - left - 1 bounded_height = min(height[left], height[i]) - height[bottom] ans += width * bounded_height stack.append(i) return ans逐行解释一下核心循环。当 height[i] > height[stack[-1]] 时，先把栈顶元素弹出来，它就是当前凹槽的“底部”bottom。弹完以后检查栈是不是空了，如果空了，说明这个 bottom 左侧没有更高的柱子，形不成左边界，水会流走，直接 break，不结算这一块。如果栈还非空，新的栈顶 left 就是左边界，当前 i 就是右边界。于是宽度 = i - left - 1，这个宽度可能会大于1，因为它跨越了中间所有柱子。高度 = min(height[left], height[i]) - height[bottom]，左右边界中较矮的那个决定了水位上限，减去底部高度就是实际水深。两者相乘就是这一整块横向水的体积，累加到 ans 里。
4.3 用小例子把多级结算看明白
单调栈初看很绕，尤其遇到连续凹槽时会触发多轮结算。我用 height = [3, 0, 2, 1, 4] 来演示，这个例子总水量也是6。栈里表示法为“下标(高度)”。
| i | height[i] | 动作 | 结算水量 |
|---|---|---|---|
| 0 | 3 | 入栈：[0(3)] | - |
| 1 | 0 | 0≤3，入栈：[0(3),1(0)] | - |
| 2 | 2 | 2>0，弹出1作为bottom，左边界0，宽度=2-0-1=1，高度=min(3,2)-0=2；然后2≤3，入栈 [0(3),2(2)] | 2 |
| 3 | 1 | 1≤2，入栈：[0(3),2(2),3(1)] | - |
| 4 | 4 | 4>1：弹出3，左边界2，宽度=4-2-1=1，高度=min(2,4)-1=1；4>2：弹出2，左边界0，宽度=4-0-1=3，高度=min(3,4)-2=1；4>3：弹出0，栈空break；最后入栈 [4(4)] | 4 |
累计水量：2 + 1 + 3 = 6。关键在高潮部分：当 i=4 时，while 循环一口气弹了三层。第一次弹的是高度1，底是1，左右边界是高度2和高度4，算1格水。第二次弹的是高度2，底是2，左边界是高度3，右边界是高度4，宽度是3，高度是1，一次就结了3格水。这就是“横向结算”的威力，一个弹出动作覆盖了位于位置1、2、3三个格子的水位。这也是单调栈题解里最容易让人看不懂的地方，强烈建议在纸上把这个过程完整推一遍，比反复看答案管用得多。
5. 四种解法横向对比与面试怎么答
5.1 一张表看懂复杂度
| 解法 | 时间复杂度 | 空间复杂度 | 核心思想 |
|---|---|---|---|
| 暴力法 | O(n²) | O(1) | 每个位置分别扫描左右求最大 |
| 动态规划（前后缀数组） | O(n) | O(n) | 用数组缓存每个位置的左右最大 |
| 双指针 | O(n) | O(1) | 左右指针收缩，谁矮结算谁 |
| 单调栈 | O(n) | O(n) | 用递减栈逐块结算凹槽水量 |
单调栈虽然空间开销同样是 O(n)，但它的思考方式和双指针完全不同，是另一种模型。在实际比赛中或者面试追问“还有别的思路吗”的时候，能主动给出它，说明你对数据结构的理解不是只会背模板。
5.2 面试递进策略：别上来就甩最优解
面试最忌讳的就是把最优解当标准答案背出来，却讲不清楚思考过程。不管是我自己面试，还是身边人做面试官的经验来看，面试官更想看到你怎么一层一层优化。推荐这么组织：
先讲暴力思路，一句话带过，主动说“这个显然太慢，我可以优化到 O(n)”。然后写动态规划版本，区间扫描三趟，代码干净，五分钟左右写完。接着口头说一下双指针，重点表述“因为矮的那侧决定水位，所以谁矮谁决定能不能先结算”，如果面试官示意你写，就快速写一版。最后补一句“另外这题还能用单调栈逐块结算，时间复杂度 O(n)，空间 O(n)，不过通常双指针就够了”。这样整个回答的节奏是主动递进的，而不是被动掏答案。
5.3 写代码时的三个加分细节
写算法题也有“软实力”得分点。变量名用 left_max、right_max、left、right、ans 这种自解释的命名，别写 a、b、c。边界判断提前返回，n<3 直接返回0。还有，三种解法一定都要亲手写一遍，哪怕背也能背下来，但默写和看着答案照抄完全不是一回事。我见过不少候选人，双指针代码写得飞快，让他用手推一遍就卡壳，这种“手比脑子快”的状态在压力面试下是藏不住的。
6. 常见坑位与调试经验速查
6.1 边界条件：数组长度小于3直接返回0
一根柱子接不住水，两根柱子也接不住，水一定会从较矮那侧流走。函数开头先判断 n < 3 返回0，既省事又安全，还能避免后面循环里出现各种越界或奇怪的边界计算。另外暴力法的遍历范围记得控制为 1 到 n-2，因为端点位置没有两侧条件，不可能积水，逻辑上也说得通。
6.2 双指针的三个隐蔽坑
第一个坑是初始化顺序。如果 leftMax 初始化为 height[0]、rightMax 初始化为 height[n-1]，循环里就先结算后移动；如果初始化为0，就先更新后结算。两种写法等价，但很多人把两种写法混着用，结果要么漏掉边缘柱子，要么算出负数。我建议统一用“先更新，再结算”这一种，逻辑上最不容易出错。
第二个坑是相等情况的处理。leftMax 和 rightMax 相等时走左分支还是右分支，结果完全一样。关键在于不要同时依赖两侧的结算逻辑，保持一个 consistency 的写法。第三个坑是 leftMax 的语义。它不是全局最大值，而是 left 左侧包括 left 自己的最大值。随着指针移动，leftMax 会被不断抬高，这个“动态门槛”是双指针正确性的核心，也是最容易被忽略的。
6.3 单调栈的坑位三连
单调栈代码短，但易错点非常多。第一个坑是弹出 bottom 后栈为空，必须 break。如果写 continue，或者干脆忘了处理，下一步访问 stack[-1] 会直接越界，在语言里表现为运行时错误。第二个坑是结算高度写错。正确公式是 min(height[left], height[i]) - height[bottom]，也就是当前凹槽左右边界柱子的高度取小再减底部。有人会顺手写 min(left_max, right_max) 那种全局值，这就完全错了，这一块凹槽和全局最高点没有直接关系。第三个坑是当前 i 必须最终入栈。很多新手在 while 结算之后忘了 stack.append(i)，栈里缺了元素，后面的凹槽就再也没有机会被正确结算。这三个坑我几乎在每个人身上都见过，写的时候自己也要多留个心眼。
6.4 三道兄弟题，学会触类旁通
接雨水不是一座孤岛，把它和几个关系最近的题目放在一起刷，效果翻倍。盛最多水的容器，同样双指针，求两根柱子能蓄的最大面积，核心判定也是“短板决定水位”，移动较矮的边。柱状图中最大的矩形，也是单调栈，但栈是递增的，遇到更矮的柱子才触发计算，结算的是以某根柱高为高的最大矩形，方向正好和接雨水相反。二维接雨水则是真正的升级版，用最小堆从外边界向内收缩，每次从小堆顶扩散，思路从“找两侧短板”变成了“找一圈最短的墙”，非常锻炼人对优先队列的理解。这几道题共同的内核都是找边界、找短板，差别只在于是竖着找还是横着找、是二维还是三维。
我个人刷这题的习惯是至少三刷。第一遍看答案理解思路，第二遍关掉书默写双指针，第三遍把动态规划、双指针、单调栈三种解法全部用手推一遍例子，尤其要把单调栈那种多级横向结算的过程亲手推完整。如果你在纸上模拟双指针总是推不到正确答案，试试把每一轮更新后的 left、right、leftMax、rightMax、ans 五个值列成一张表，对照代码从头过一遍，往往十秒钟就能发现自己漏了哪一步。这道题值不值得刷三遍？从它出现在面试里的频率来看，太值得了。
估计目标与敏感性分析：临床试验治疗效应的定义与落地)
