1. 这个trap到底在装什么水1.1 题目速览接雨水到底在算什么接雨水Trapping Rain Water是 LeetCode 第 42 题也是单调栈这个数据结构最经典的出场场景之一。题目本身很短给你一个非负整数数组height每个数字代表一根宽度为 1 的柱子的高度问下过雨后这些柱子之间总共能存多少水。示例[0,1,0,2,1,0,1,3,2,1,2,1]的答案是 6这个结果我一开始怎么都看不出来后来才知道要先学会把空间切成水层。第一次刷这题的人通常分两派一派觉得简单不就是找些凹坑然后逐个加吗另一派完全懵不知道从哪里下手、从哪里结束。我是第二派。直到我换了一个视角积水不是一个坑一个坑孤立存在的而是被左右两根更高的柱子夹出来的。任何一格能不能存水取决于它左边最高柱和右边最高柱里较矮的那根再减去自身高度。这个看上去很朴素的观察最后演化出了四种主流解法其中结构最优雅、最能和面试官聊出深度的就是单调栈。这篇文章我打算从一个很偏的角度切入——先聊聊英文题名里的 trap 到底困住了什么然后完整拆解单调栈的推导、代码、手推样例和边界坑。单调栈解法本身只有十行左右但十行背后的那层窗户纸值得认真捅破。1.2 trap 的双关从 charge trap 和 floating gate 说起我特别喜欢这题的英文名里 trap 这个词。在半导体存储领域有两个跟困住密切相关的概念floating gate浮栅和 charge trap电荷陷阱。传统闪存用浮栅存电子——一个完全被绝缘层包裹的导体层电荷一旦注入进去就被困在势垒里出不来后来工艺继续缩小出现了 charge trap flash改用氮化硅里的分立陷阱态来困住电子比连续导体层更容易微缩也让 3D NAND 成为现实。讲这个不是为了掉书袋而是困住这事儿的本质是相通的想困住任何东西必须先有边界。电荷困得住是因为四周绝缘层构成了势垒雨水困得住是因为左右两根更高的柱子构成了墙。你在做接雨水这道题时从头到尾只干一件事——反复确认某个凹槽的左边墙、右边墙和坑底分别在哪里。墙找对了水自然算得出来墙找错了答案就离谱。想通这一点算法题就不再是背代码而是一种找边界的思维训练。1.3 四种主流解法先画张全景图在敲单调栈之前必须知道这题还有其他做法。因为面试时大概率会被追问还有没有更优解你至少得能说出四种方案的差异。解法核心思想时间复杂度空间复杂度难点暴力每个位置分别向左、向右找最高柱子O(n²)O(1)慢但最容易理解前缀/后缀最大值DP预处理 leftMax[i] 和 rightMax[i] 数组O(n)O(n)思路直给代码好写双指针左右夹逼动态维护两侧最大值O(n)O(1)数学技巧性强不太好懂单调栈用单调递减栈维护可能的左墙候选O(n)O(n)理解门槛最高代码最短我的个人看法双指针在复杂度上确实最优但初学阶段最推荐先写 DP 版因为它最贴近每根柱子看左右最高的直觉单调栈的价值在于它把扫描过程中发现凹槽这件事完完整整地模拟了出来。双指针考验的是数学观察力而单调栈考验的是结构感——所以你如果想把数据结构和算法内化单调栈这题绕不过去。2. 单调栈为什么能解这道题2.1 把视角从柱子切换到凹槽我最早犯的错误是站在每根柱子的角度问自己这一根柱子能存多少水结果中间矮的柱子看似能存不少等换了边界答案又对不上越算越乱。后来我才意识到人的直觉是数柱子但自然的物理过程是积水填坑——水是一层一层漫进凹槽里的不是一格一格挂在柱子上的。看一个最朴素的例子高度[2, 1, 1, 2]。从左往右扫扫到前三个柱子时什么都不能确定因为还不知道后面会不会出现右墙等扫到最后一个 2 时我们发现它比中间的 1 高于是形成了凹槽。这个过程用栈描述非常自然柱子们先进栈等遇到能当右墙的柱子时再回头把之前存着的信息取出来结算。这里有一个关键点右墙并不一定要比左墙高只要比坑底高水就能存。示例里最后那个 2 比第一个 2 等高照样把中间的洼地填满了。真实数据里同一个大水坑往往会被多个右墙分阶段填满这正是单调栈解法最精妙之处——它不奢求一次性识别出完整的大坑而是每遇到一面可能的右墙就当场结算掉一层能确定的水。2.2 单调栈到底维护了什么单调栈在这题里维护的是到目前为止还没找到右墙的柱子下标并且它们的高度从栈底到栈顶严格递减。你可以把栈想象成一条从高到低的下坡路——栈底是最远处的高墙栈顶是当前最低点也是下一个凹槽最可能的坑底。为什么要严格递减因为低处才有资格当未来的坑底。只要新来的柱子比栈顶矮它就不可能成为任何人的右墙先入栈候着一旦新来的柱子比栈顶高它就有了当右墙的潜质于是触发结算。这里的严格两个字别忽视——如果出现相同高度用判断就不会触发结算干净利落如果写成虽然一样能算出正确答案但会平白多几次弹出和加 0 水量的无效计算面试时容易被追问细节。另一个容易踩的误区是栈里存什么。答案是下标不是高度。因为计算水量需要宽度而宽度等于右墙下标减左墙下标再减 1。如果只存高度算完高度发现没有宽度信息代码立刻僵住。这也是很多初学者第一版代码写一半写不下去的原因。下标是个索引通过它既能拿到高度也能参与宽度计算一举两得。2.3 结算公式到底怎么来的假设当前扫描到下标i高度为height[i]且它大于栈顶对应的高度。此时触发一段结算逻辑弹出栈顶记为bottom——这是坑底。如果栈空了说明bottom左侧没有比它更高的墙无法形成凹槽直接跳过。如果栈没空新的栈顶记为left——这是左墙当前下标i是右墙。这一层水的宽度是width i - left - 1。这一层水的高度是depth min(height[left], height[i]) - height[bottom]。为什么高度要取 min因为水面是平的水一定会从矮的那面墙溢出所以实际存水深度由矮墙决定。同时由于栈内高度严格递减height[bottom]必然小于height[left]所以depth一定非负不会算出负水量。用[2, 1, 1, 2]推一遍扫到 i3 时先弹出下标 2 的高度 1栈顶变成下标 1 的高度 1width 3 - 1 - 1 1depth min(2,2) - 1 1累加 1再弹出下标 1 的高度 1栈顶变成下标 0 的高度 2width 3 - 0 - 1 2depth min(2,2) - 1 1累加 2。总水量 3。你看同一个大水坑被拆成了两层来算先算最深的一层再算宽一些的一层。这就是水层视角——它把积水分层而不是分柱是理解单调栈解法的钥匙。2.4 为什么单调栈值得单独掌握和 DP 解法对比一下会更清楚。DP 是每个位置都提前算好左右最大值再按格累加思路是静态的单调栈是扫描过程中动态发现并结算凹槽思路是动态的。前者把每个格子孤立地看后者把柱子之间的联系串起来了。从训练价值来说我强烈建议你把单调栈写在纸上演算一遍。因为这种入栈、发现右墙、循环结算的模式不止出现在接雨水里——柱状图中最大的矩形、每日温度、滑动窗口最大值全都能用单调栈解。花一小时吃透这一题相当于同时预习了四五道经典题这买卖很划算。3. 完整实现与手推过程3.1 Python 实现逐行注释def trap(height): stack [] # 栈里存下标高度从栈底到栈顶严格递减 ans 0 for i, h in enumerate(height): # 当前柱子比栈顶高说明它可能成为右墙 while stack and h height[stack[-1]]: bottom stack.pop() # 坑底 if not stack: # 栈空 没有左墙结算不了水 break left stack[-1] # 左墙 width i - left - 1 # 水层宽度 depth min(height[left], h) - height[bottom] # 水层高度 ans width * depth stack.append(i) # 当前柱子入栈作为未来候选 return ans这个版本我实际提交过能直接通过所有测试用例。重点看 while 循环里为什么是 结算完后继续看新的栈顶——因为一面右墙可以同时给好几层凹槽当墙。比如[5,1,1,5]最右边的 5一口气结算了两层水这个行为全靠 while 的持续循环来完成。你如果只写 if答案立刻变小这是新手最容易忽略的地方。3.2 C 版本换语言不换逻辑int trap(vectorint height) { stackint st; int ans 0; for (int i 0; i (int)height.size(); i) { while (!st.empty() height[i] height[st.top()]) { int bottom st.top(); st.pop(); if (st.empty()) break; int left st.top(); int width i - left - 1; int depth min(height[left], height[i]) - height[bottom]; ans width * depth; } st.push(i); } return ans; }C 版和 Python 版逐行对应。唯一提醒是(int)height.size()的强转避免 size_t 无符号类型在空数组时参与比较引发问题。还有min在 C 里默认比较的是值这里传入的是两个高度值没问题。3.3 手推标准样例一步步看着水被算出来拿题目示例[0,1,0,2,1,0,1,3,2,1,2,1]完整走一遍。下表里的栈内容指操作结束后的栈栈中元素是下标。iheight[i]操作本次累加ans栈内容00入栈 000[0]1110弹 0栈空 break入栈 100[1]2001 否入栈 200[1,2]32弹 2left1width1depth1再弹 1栈空 break入栈 311[3]4112 否入栈 401[3,4]5001 否入栈 501[3,4,5]61弹 5left4width1depth111 否入栈 612[3,4,6]73弹 6left4width2depth0弹 4left3width3depth1弹 3栈空 break入栈 735[7]8223 否入栈 805[7,8]9112 否入栈 905[7,8,9]102弹 9left8width1depth122 否入栈 1016[7,8,10]11112 否入栈 1106[7,8,10,11]最终 ans 6和预期一致。这张表我建议你自己在纸上重画一遍尤其是 i6 和 i7 这两步它们分别演示了结算后立刻停和一个右墙连续结算多个水层两种典型场景。画过一遍之后你就再也不会忘记 while 循环的存在了。3.4 最容易写错的两个点第一弹出bottom之后必须检查栈是否为空。因为左墙是从新的栈顶拿的如果栈空了说明这个坑底左边没有更高的边界水根本存不住。很多初版代码在这里要么直接越界要么算出一个巨大的错误宽度。记住if not stack: break这句是安全阀不是可有可无。第二宽度公式里的left是新的栈顶不是刚弹出的bottom。我见过很多版本写成了i - bottom - 1把宽度凭空拉大好几格答案自然偏大。调试这类问题最快的方法是打印出每一次结算时的bottom、left、width、depth四个值对照手推表一眼就能定位是哪个环节出了问题。4. 边界条件与踩坑记录4.1 边界用例清单直接拿去测刷算法题最怕提交前自我感觉良好提交后一片红。以下是我长期保留的一组自测用例height []期望 0height [1]期望 0height [1,2]期望 0只有两面墙没有坑height [3,3,3,3]期望 0等高没有凹槽height [0,1,0,2,1,0,1,3,2,1,2,1]期望 6height [4,2,0,3,2,5]期望 9height [0,1,2,3,4]期望 0严格递增右墙永远比左墙晚到或不到height [4,3,2,1,0]期望 0严格递减永远没有右墙height [5,1,1,5]期望 8连续结算两层height [2,1,1,2]期望 3等高的左右墙也能存水把这组用例封装成一个测试函数每次改完代码先跑一遍再提交能帮你省下大量试错时间。特别是严格递增和严格递减这两个用例专门用来验证栈空时正确跳过结算的逻辑非常有效。4.2 我踩过的几个真实坑第一个坑栈里存高度而不是下标。第一版代码写完算到宽度时发现手里只有高度值完全没有坐标信息只能干瞪眼。后来彻底想明白下标索引是算法题的万能钥匙拿到下标的一瞬间高度、宽度、位置关系全部解锁。以后凡是涉及区间宽度的栈类题目我默认先考虑存下标。第二个坑把 while 比较方向写反。曾经把height[i] height[stack[-1]]写成height[i] height[stack[-1]]结果单调递减栈变成了单调递增栈整个逻辑反了。后来我养成了一个习惯写单调栈前先在草稿纸上画一根横轴、几根柱子的简笔画然后问自己新来的柱子比栈顶高意味着什么——高才有资格当右墙矮只能当候选坑底。第三个坑while 只写了一次没写循环。还是[5,1,1,5]这个用例右墙 5 明明能连续结算两层水如果代码里只if一次答案直接少一半。单调栈解法的灵魂就在这个持续向左回溯的 while 上一旦漏掉正确性全毁。4.3 复杂度分析为什么这个解法是 O(n)时间上每个下标最多入栈一次、出栈一次while 循环总执行次数不会超过元素个数所以整体时间复杂度 O(n)。空间上最坏情况是严格递减数组比如[5,4,3,2,1]所有元素都会留在栈里等待永远不出现的右墙空间 O(n)。这里有个面试加分点你可以主动提一句接雨水的本质是向右找第一个能当右墙的更高柱子同时向左借助栈结构找到左墙这和下一个更大元素系列题是同一套思维。如果你能进一步说出这题和 LeetCode 84 柱状图中最大的矩形用的是同一种单调栈只是那个是维护递增栈、找左右两边更矮的边界面试官基本就能确定你是真懂而不是背题。4.4 变体和扩展方向如果输入数组特别大比如千万级别单调栈 O(n) 的空间可能有点吃紧可以改用双指针把空间压到 O(1)。如果柱子宽度不等变成不同宽度的平台单调栈照样能用只要把宽度公式从i - left - 1改成实际坐标差逻辑不用大改。更进阶的玩法是二维接雨水LeetCode 407从一维凹槽升级成从外向内灌水解法变成了优先队列加 BFS但核心思想一脉相承——水能被困住的前提依然是四周存在更高的边界。如果你能把一维单调栈理解通透再去啃二维会有一种原来如此的顺畅感。5. 常见问题速查手册下面这个表我整理了很久把刷题社区里关于单调栈解接雨水的典型问题都列了出来按现象—原因—对策三列组织。现象可能原因对策答案偏大宽度错误地用了bottom到i的距离改成i - left - 1left 是弹栈后的新栈顶程序崩溃或越界弹出 bottom 后没有判栈空在取 left 之前加if not stack: break递增数组返回非 0结算逻辑没有正确跳过无左墙场景检查栈空分支是否在所有路径上都生效严格递减数组返回非 0右墙始终不出现但代码误判了某种边缘情况确认 while 条件是而不是等高柱子场景出错比较符号用错导致边界语义混乱统一使用让等高柱子保持栈内秩序连续多层积水漏算while 写成了 if确认结算过程放在 while 循环内部栈里存了值而不是下标设计时没考虑宽度计算改成存下标通过height[stack[-1]]取高度另外有一个小疑问我见过不少人问为什么min(height[left], height[i]) - height[bottom]可能等于 0答案很简单当凹槽底部和某一边界高度相等时这层水高度为 0。比如栈里存在一段等高序列时就会出现这种白算的情况但不影响最终正确性。这里千万别为了跳过低效计算去改比较符号保持代码语义清晰比省几微秒重要得多。6. 最后分享一点实战体会这道题我前前后后重写了不下十遍每次重写都有新收获。第一次写是背代码换一个用例就不会了第二次写才真正理解 while 循环存在的原因第三次开始尝试自己推导width和depth公式才彻底和水层视角和解。如果让我给一个可复现的学习路径它是这样的先用暴力法把答案算对建立信任感再写 DP 版理解左右最高值这个核心概念然后写单调栈版重点体会从静态计算到动态结算的转变最后看双指针版理解如何用数学观察把空间省掉。四步走完这一题就真正变成你的了。最后再分享一个小技巧我本地一直保留着一个接雨水测试台里面放着这章列出的十个边界用例。每次学习新的栈相关算法我都会拿它来当基准测试顺带验证自己有没有把逻辑写死。这个习惯帮我省了无数次提交失败带来的返工时间——毕竟一遍过的快乐只有刷题人才懂。