在算法面试里单调栈这仨字一出来很多人的第一反应是听过但不知道什么时候用。而 LeetCode 第 42 题接雨水Trapping Rain Water恰恰是把它推到台前的最佳载体。这题表面看是个数组题刷多了你会发现它其实在考一个很本质的东西你能不能跳出逐个格子算的惯性转而去捕捉坑的结构——而单调栈就是为这种结构而生的工具。这篇文章我不打算只是贴个能过的代码。我会把单调栈解法里最容易让人懵的地方——为什么栈底到栈顶是递减的、为什么出栈时才算接到水、宽度为什么是i - stack[-1] - 1——全部拆开讲透再附上完整的可运行代码和踩坑总结。无论你是面试前突击还是单纯想弄懂这题这篇都值得花十分钟读完。1. 接雨水的直觉陷阱为什么暴力解会把复杂度打上天1.1 题目的真实场景先明确问题本身。给定n个非负整数每个数代表宽度为 1 的一根柱子的高度。下雨之后这些柱子之间能存住多少水LeetCode 给的标准示例是[0,1,0,2,1,0,1,3,2,1,2,1]答案 6。看到这种问题人脑第一反应其实是看凹槽哪里低、两边哪里高中间就能兜住水。但把这个直觉翻译成代码绝大多数人会直接掉进第一个坑——按柱子逐个扫对每个柱子向左右分别找最高墙。说起来很顺某个位置能存的水等于min(左侧最高, 右侧最高) - 当前高度如果结果是正数就累加。def trap_brutal(height): n len(height) ans 0 for i in range(n): left_max max(height[:i1]) # 实际应写循环取左侧最高 right_max max(height[i:]) # 实际应写循环取右侧最高 ans max(0, min(left_max, right_max) - height[i]) return ans这个解法好不好答案是对的但每个位置都做一次全范围扫描时间复杂度是 O(n²)。LeetCode 上这题的n上限是2 * 10^4O(n²) 就是 4 亿次操作Python 跑起来会明显卡顿勉强能过测试但没有任何面试亮点。更关键的是这个解法暴露了一个思维盲区它把每个位置孤立地当成一个格子而忽略了柱子之间的前后依赖关系。1.2 水能存多少取决于墙而非格子我见过很多人卡在接雨水这道题上本质上不是不会写代码而是没想明白一个物理事实一个位置能不能积水不取决于它自己有多矮而取决于它左右两边是否真的有墙把它围住。而且这两堵墙之间往往隔着好几个柱子。拿[2, 1, 0, 1, 3]来说中间三个位置都能存水但存水的左墙其实是下标 0 的 2右墙是下标 4 的 3。中间下标 1、2、3 连成一片共同构成了一个大的凹陷区域。如果你按单个格子算会发现下标 2高度 0的左右墙分别是 1 和 1只能存 1 格水——这没错但下标 1高度 1同样是左右墙 1 和 1存 0 格。这三个格子各自算出来的结果加在一起恰好等于整个凹陷能接的总水量 3。这个例子的启发是接雨水本质上是一个区域问题不是一个点问题。想高效求解你就需要一种能记住之前见过谁、并且回头清算的数据结构。这正是栈出场的地方——它能让你从左到右扫一遍遇到右墙时回头把之前攒着的坑底一个个弹出来结算。2. 为什么单调栈能天然匹配找坑这件事2.1 从单调到低谷一个反直觉的视角转换单调栈听起来很高深拆开就两句话栈内元素按某种顺序排列要么从栈底到栈顶递增单调递增栈要么递减单调递减栈。关键是什么时候用递增、什么时候用递减这取决于你想找的是下一个更大元素还是下一个更小元素。接雨水用的单调栈我试过不少写法最顺的是维护一个高度单调递减的栈。什么意思从左往右遍历柱子时只要当前柱子比栈顶柱子矮就把它压进去——栈里的高度就保持从底到顶递减。一旦遇到比栈顶高的柱子栈顶那个矮柱就成了一个坑底而当前这根高柱就是坑的右墙栈里紧挨着坑底的那根柱子就是左墙。你可以把单调栈想象成在连绵起伏的山里边走边记录一路下坡时经过的洼地。只有在下坡结束、开始上坡时你才真正看到刚才那个洼地的深度。同理只有新柱子比栈顶高时之前的洼地形状才算完整可以结算水量。这就是单调栈解决接雨水的核心视角转换站在填坑的角度看而不是站在数水的角度看。你不需要知道全局最高墙在哪你只需要知道当前这堵右墙和刚刚弹出的坑底以及坑底左边最近的墙之间能不能形成一个局部蓄水区。2.2 栈里存什么下标不是高度初学者最容易犯的错是在栈里存高度值。一定存下标。原因有三个算宽度需要左右墙的位置差右墙下标减去左墙下标再减 1就是你这次能接水的水平宽度。只有下标才能做减法存高度算不出宽度。算高度需要找栈中下一个元素坑底弹出后新的栈顶就是左墙你要拿它去和右墙高度取最小值。这个弹出后看新栈顶的操作天然依赖栈里存的是带顺序的下标。高度相等的情况需要靠下标区分两个同为 2 的柱子虽然高度一样但它们围出的宽度区域可能跨了多个柱子没法用高度值表达。栈底永远是当前扫描过的、尚未被更高的右墙触发结算的柱子。栈顶则永远是目前扫描范围内右边最低的柱子——因为一旦有比它矮的矮的会压在它上面一旦有比它高的它就被弹出去结算了。3. 单调栈解接雨水的完整实现逐行拆给它看3.1 代码先跑起来话不多说直接上能 AC 的标准写法。我用 Python 写因为结构最清楚思路看懂后翻译成 Java 或 C 都很容易。def trap(height): 用单调递减栈求接雨水量 时间复杂度 O(n)空间复杂度 O(n) if not height: return 0 n len(height) stack [] # 单调递减栈存柱子下标 ans 0 for i in range(n): # 当前柱子比栈顶高说明形成了坑准备结算 while stack and height[i] height[stack[-1]]: top stack.pop() # 弹出的是坑底当前最低点 if not stack: # 左边没有墙形不成存水区 break left stack[-1] # 新栈顶 左墙下标 width i - left - 1 # 水平宽度左右墙之间隔了多少个柱子 h min(height[left], height[i]) - height[top] # 能积水的有效高度 ans width * h stack.append(i) # 当前柱子入栈等待未来被结算 return ans把示例[0,1,0,2,1,0,1,3,2,1,2,1]跑一遍输出 6通过。但跑通只是最低要求下面我会把每行代码背后的物理意义讲清楚。3.2 while 循环触发的是结算时刻很多人看不懂这段代码关键在于不理解while循环在干什么。它在做的不是边扫边存水而是等到右墙出现的那一刻回头一次性结算掉之前所有能存水的位置。比如遍历到下标 3高度 2时栈里的下标是[0, 1, 2]对应高度是[0, 1, 0]。此时height[3] 2比栈顶的高度 0 大于是触发 while弹出栈顶下标 2高度 0这是坑底。新栈顶是下标 1高度 1这是左墙。右墙是当前下标 3高度 2。宽度 3 - 1 - 1 1就是下标 2 这一个柱子。高度 min(1, 2) - 0 1。面积 1 * 1 1累加。这就是下标 2 那个凹槽接的 1 格水。注意这里结算完之后栈变为[0, 1]。接着循环继续判断height[3] 2 height[1] 1再次触发结算弹出栈顶下标 1高度 1这是新的坑底。新栈顶是下标 0高度 0这是左墙。右墙仍是当前下标 3高度 2。宽度 3 - 0 - 1 2横跨下标 1 和 2 两个位置。高度 min(0, 2) - 1 -1等等负的这里就出现了一个必须处理的细节——min(0, 2) 0减去坑底高度 1 后是负数说明这个坑的左墙根本不够高攒不住水。而我们的代码里没有显式判断正负为什么还能得到正确答案3.3 负数高度的真实含义与代码的隐形保护回到刚才的情况min(0, 2) - 1 -1宽度 2乘积是 -2累加进去不就错了吗不会因为注意 while 循环里有一行提前 breakif not stack: break在弹出下标 1 之后栈还剩一个下标 0。此时我们没有 break继续走。但min(0, 2) - 1 -1是负的按理说该出问题…… 实际上细看发现这里我的示例不够严谨。让我给一个更干净的触发场景[3, 2, 1, 2]。下标 03入栈栈 [0]下标 12入栈栈 [0, 1]下标 21入栈栈 [0, 1, 2]下标 32触发 while弹出栈顶 2高 1栈 [0, 1]left 1高 2width 3-1-1 1h min(2,2) - 1 1ans 1。继续判断height[3] 2 height[1] 2不是大于是等于while 停止。下标 3 入栈栈 [0, 1, 3]。这个过程完全没问题结算的都是正的。刚才[2,1,0,1,3]里的负数情况我在哪一步弄混了让我重新理一遍height [2, 1, 0, 1, 3]下标 02入栈栈 [0]下标 11入栈栈 [0, 1]下标 20入栈栈 [0, 1, 2]下标 31触发 while弹出栈顶 2高 0栈 [0, 1]left 1高 1width 3-1-1 1h min(1,1) - 0 1ans 1。继续判断height[3] 1 height[1] 1等于while 停止。下标 3 入栈栈 [0, 1, 3]。下标 43触发 while弹出 3高 1栈 [0, 1]left 1高 1width 4-1-1 2h min(1,3) - 1 0ans 0。继续判断height[4] 3 height[1] 1是弹出 1高 1栈 [0]left 0高 2width 4-0-1 3h min(2,3) - 1 1ans 3。总 ans 1 3 4。这个例子里根本没有负数。我刚才说的负数情况其实不会出现是因为 while 循环的触发条件是height[i] height[stack[-1]]也就是右墙一定比坑底高而左墙高度是height[stack[-1]]新栈顶它可能是 0此时min(左墙,右墙)可能小于坑底高度结果确实可能是负的。比如栈里是[0, 1]height 是[0, 1]当前高度 5弹出 1 后左墙是 0min(0, 5) - 1 -1。那代码为什么没错因为这种情况要积累到足够宽才会出现而实际上仔细算负的结果乘以正宽度会污染答案。但 LeetCode 的测试用例里[0,1,1,5]这种形状不存水所以有些实现里不加正负判断也能过——这其实是隐患。稳妥的写法是water min(height[left], height[i]) - height[top] if water 0: ans width * water加一个正数判断逻辑无懈可击。很多题解里省略这一步不是因为它是对的而是因为恰好没碰上把次数算成负数的用例。我会建议你在自己的代码里加上面试时主动提这个细节考官印象会好很多。4. 和暴力、双指针、动态规划放在一张桌上对比4.1 三种主流思路的复杂度与适用边界接雨水这道题的经典解法不止单调栈一种。为了让你面试时不慌我把主流的四条路都摆出来对比一下。解法时间复杂度空间复杂度核心思路适用场景暴力扫描O(n²)O(1)每个位置看左右最高墙数据量极小比如 n 100前缀最高值动态规划O(n)O(n)预计算每个位置左右最高墙一次遍历求和侧重思路简单、代码不易错双指针O(n)O(1)左右指针维护已验证的最高墙哪边矮结算哪边要求最省内存面试最推荐之一单调栈O(n)O(n)按坑结算遇到高墙回头统一处理变形题多、后续想学下一个更大元素类题型暴力解法是我们开头见过的不多说。动态规划解法的思路是从左往右扫一遍记录每个位置左边的最高墙left_max[i]再从右往左扫一遍记录右边的最高墙right_max[i]最后每个位置能存的水就是min(left_max[i], right_max[i]) - height[i]的正数部分。这个解法本质上是空间换时间把重复的扫描结果缓存下来。它和单调栈的区别在于动态规划是每个位置单独算单调栈是按整个坑统一算。两者最后答案一样但思考模型完全不同。双指针解法是我个人最喜欢在面试时先讲的方案因为空间 O(1) 且思路很优雅左右两个指针往中间走维护left_max和right_max哪边的最高墙更矮就结算哪边当前指针的积水量然后把指针向中间挪一步。因为最终水量由矮的那边决定所以矮的那边可以直接算不需要等另一边。4.2 单调栈独有的优势不只是为这一题准备的既然双指针空间更省为什么还要学单调栈因为单调栈是一个通用工具接雨水只是它的一个应用场景。一旦你掌握了单调栈触发结算的思维模型后面遇到这些题会非常顺LeetCode 84. 柱状图中最大的矩形同样是单调栈但维护的是递增栈遇到矮柱子时弹出结算矩形面积宽度计算逻辑和接雨水几乎一摸一样。LeetCode 739. 每日温度单调递减栈找到下一个更高温度的位置入栈出栈的时机和接雨水的触发结算高度相似。LeetCode 496. 下一个更大元素经典单调栈入门题搞清楚这个再看接雨水会轻松很多。LeetCode 316. 去除重复字母困难单调栈加额外条件保障字典序最小。所以我的学习路径建议是先做 496 和 739 熟悉单调栈的入栈出栈再做 42 理解按坑结算最后挑战 84 和 316。这个顺序下来你对单调栈的掌握会远比背一道题扎实。4.3 什么时候别用单调栈警惕思维定式不过我也得泼一盆冷水接雨水不是非单调栈不可甚至单独看这题双指针是更优解。如果面试时你只会单调栈一旦面试官追问能不能把空间优化到 O(1)你就被动。所以仅仅会一种解法是不够的。我的建议是面试答这题时先把暴力思路一句话带过表明你懂问题本质然后给出双指针或单调栈最后主动提一句这题还能用单调栈做核心是按坑结算。这样既展示广度又展示深度。实际工作中刷题不是为了炫技而是为了锻炼把问题抽象成已知模型的能力。单调栈的抽象模型就是找下一个更大/更小的转折点这个模型很值钱值得你花时间彻底吃透。5. 单调栈写法的边界细节与调试心得5.1 栈空、等高、负数水量三个最容易翻车的地方写单调栈解接雨水90% 的 bug 出在这三处。我一个个说这些全是血泪经验。第一栈空必须先判断。弹出坑底后如果栈空了说明左边没有墙直接 break 或 continue不参与结算。比如[3, 2, 1]这种只在下降的数组一个水都存不了但如果你不处理栈空代码会在stack[-1]处抛 IndexError。第二等高的柱子别乱弹。while 循环的触发条件是height[i] height[stack[-1]]用的是严格大于不是大于等于。为什么不能大于等于以[2, 2, 1, 2]为例。如果使用在下标 1高度 2时就会把下标 0 弹出此时栈空什么也算不了而用严格两个同为 2 的柱子会都留在栈里后续遇到更高的右墙时它们能作为连续的左墙参考宽度计算更准确。等高的墙体虽然高度相同但它们分别标记了不同的水平位置不能因为高度相等就合并。很多题的坑都出在这里。第三结算的宽度用左右墙下标差减 1。别直接用i - top那样会把坑底自己占的那一格宽度错误记成 1而实际上下标top已经弹出当前下标i和左墙stack[-1]之间隔了多少个旧柱子才是真正的蓄水宽度。比如[3, 1, 2]计算下标 1 的坑时左右墙下标是 0 和 2宽度应该是 1i - top却等于 2完全错误。这是个非常隐蔽的细节我见过好几个刷题群里的老手都在这翻车。为了更好理解我给 5.3 小节附一个完整的调试示例。5.2 可视化调试法用栈状态表代替干瞪眼如果你还是没完全转过来我教你一个笨但极有效的方法把每次循环后的栈、当前下标、累计答案画成一张表。拿[4, 2, 0, 3, 2, 5]为例手动走一遍当前下标 i当前高度操作栈内容下标累计 ans04入栈[0]012入栈[0, 1]020入栈[0, 1, 2]033弹出 2结算 1继续弹出 1结算 3[0, 3]442入栈[0, 3, 4]455弹出 4结算 1弹出 3结算 4[]9最终答案 9和手动算的完全一致。你可以在电脑上跑一遍这个表再对照代码看每一步单调栈的图像感会瞬间清晰起来。我在学习时发现光看代码永远隔层纱手动模拟三个用例之后触发结算的时机就刻进脑子了。5.3 一道五分钟自测题检验你有没有真懂试着自己推一遍[1, 0, 2, 1, 3, 1, 2]的完整出栈入栈过程看能不能得到答案 4。思路提示重点观察下标 1 被弹出时的左墙是谁、宽度是多少下标 5 和 6 之间的小坑会不会触发结算。推完再去 LeetCode 验证如果一次就对了恭喜你以后遇到任何单调栈题都有底气了。最后的实操建议就以这道题来说我的做法已经固定下来了拿到题先画柱状图标出左墙、坑底、右墙三要素再决定用哪种解法。单调栈的代码虽然只有十几行但里面藏着的触发结算存下标而非高度严格大于这三个纪律少一个都会在用例里翻车。你完全可以先照着本文代码跑通然后把三个细节改成错误版本亲眼看看报错长什么样——这比我苦口婆心说十遍都管用。等这题吃透了84 题柱状图最大矩形你会发现自己的思路顺得仿佛开挂。