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 到边缘而不是从 i1 或 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 0right n-1leftMax 0rightMax 0ans 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] 完整走一遍n12。初始 left0right11leftMax0rightMax0ans0。轮1更新 leftMaxmax(0,0)0rightMaxmax(0,1)1。01结算左侧0-00left1ans0。 轮2更新 leftMaxmax(0,1)1rightMax1。11不成立结算右侧1-10right10ans0。 轮3更新 leftMax1rightMaxmax(1,2)2。12结算左侧1-10left2ans0。 轮4更新 leftMaxmax(1,0)1rightMax2。12结算左侧1-01left3ans1。 轮5更新 leftMaxmax(1,2)2rightMax2。22不成立结算右侧2-20right9ans1。 轮6更新 leftMax2rightMaxmax(2,1)2。22不成立结算右侧2-11right8ans2。 轮7更新 leftMax2rightMaxmax(2,2)2。22不成立结算右侧2-20right7ans2。 轮8更新 leftMax2rightMaxmax(2,3)3。23结算左侧2-20left4ans2。 轮9更新 leftMaxmax(2,1)2rightMax3。23结算左侧2-11left5ans3。 轮10更新 leftMaxmax(2,0)2rightMax3。23结算左侧2-02left6ans5。 轮11更新 leftMaxmax(2,1)2rightMax3。23结算左侧2-11left7ans6。此时 left7right7循环结束ans6。你看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。栈里表示法为“下标(高度)”。iheight[i]动作结算水量03入栈[0(3)]-100≤3入栈[0(3),1(0)]-2220弹出1作为bottom左边界0宽度2-0-11高度min(3,2)-02然后2≤3入栈 [0(3),2(2)]2311≤2入栈[0(3),2(2),3(1)]-4441弹出3左边界2宽度4-2-11高度min(2,4)-1142弹出2左边界0宽度4-0-13高度min(3,4)-2143弹出0栈空break最后入栈 [4(4)]4累计水量2 1 3 6。关键在高潮部分当 i4 时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。边界判断提前返回n3 直接返回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 五个值列成一张表对照代码从头过一遍往往十秒钟就能发现自己漏了哪一步。这道题值不值得刷三遍从它出现在面试里的频率来看太值得了。