1. 从一道“网红题”说起为什么接雨水值得反复咀嚼LeetCode-42 接雨水这道题在算法题单里的地位差不多相当于健身圈的深蹲硬拉。我刷了三百多道题下来发现它几乎是所有“单调栈”教程绕不开的例题也是面试里出现频率极高的经典题。题目本身不难读懂给一组非负整数表示柱子的高度每个柱子宽度为1问下雨后能接多少水。但恰恰是这道看似简单的题背后藏着一个很重要的思维分水岭——你是背下了单调栈的模板还是真的理解了单调栈在干什么。先说我最想表达的一个观点接雨水这道题做法至少有六种——暴力、前缀最大值加后缀最大值、双指针、单调栈、动态规划、甚至手写堆加链表都能做。可为什么大家偏偏爱讲单调栈不是因为单调栈写法最简单双指针其实更省空间而是因为这道题能帮你把“单调栈到底在维护什么”这个问题想通透。想通了这一层后面LeetCode-84柱状图中最大的矩形、LeetCode-496下一个更大元素I、LeetCode-739每日温度这些题都会变得顺理成章。我这篇文章不打算把所有做法都铺开讲网上双指针和前缀和的题解实在太多了。我重点拆单调栈做法拆到什么程度呢拆到你能闭着眼睛把这个 while 循环的每一步在脑子里模拟出来拆到你能跟别人解释清楚“为什么 pop 出来的 top 能作为水位结算的基准”。如果你正准备面试、正在刷 LeetCode 热门 100 题或者刚接触单调栈觉得“看了题解会、合上题解废”这篇文章就是写给你的。我已经把单调栈相关的练习顺序、常见误区、复杂度分析一并整理在文末可以直接抄作业。2. 单调栈的“土话”理解一个帮你丢掉无用信息的筛子很多教程一上来就甩定义单调递增栈、单调递减栈栈内元素保持单调性。定义没错但我刚学的时候一直觉得哪里没通——我记住了规则却不知道这个规则到底在帮我干什么。后来我自己换了个说法单调栈是一个筛子它把所有对当前答案已经没有意义的元素提前扔掉只保留那些“未来还可能用得上”的候选者。2.1 两种栈分别帮你回答什么问题单调递增栈从栈底到栈顶严格递增也就是越往上越小用来找左侧或右侧第一个比当前元素小的元素。因为入栈时所有比当前元素大的都会被弹出留在栈里的都是比当前元素小的而栈顶恰好是离当前最近的那个“小元素”。单调递减栈从栈底到栈顶严格递减越往上越大用来找左侧或右侧第一个比当前元素大的元素。因为入栈时所有比当前元素小的都会被弹出栈里剩下的都是比当前元素大的而栈顶就是离当前最近的那个“大元素”。这两句话建议你自己写一遍别直接背书。我发现大多数人搞混单调递增和单调递减都是在“栈内存的是下标、比较的是高度”这种细节上绕晕的。你只要死记一个判断标准你想找更大的元素就用递减栈你想找更小的元素就用递增栈。原因很简单找更大元素时那些“小个子”挡在前面毫无意义必须弹掉才能让大个子露出来。2.2 为什么接雨水偏偏要用递减栈接雨水的核心是只有右侧出现更高的墙时中间的低洼才有可能存水。这句话翻译成单调栈的语言就是——我们在寻找“右侧第一个比当前柱子高的柱子”。按照上面那张对照表找右侧更大的元素对应递减栈。再往深了说一层。递减栈里存着的是什么呢是从左往右扫描以来一串高度持续走低的柱子下标。这串柱子之所以还没被弹出是因为它们至今没遇到比自己更高的右墙。一旦遍历到一个更高的柱子栈顶的那根柱子就“等到了右边界”可以开始结算水量了。而栈里更靠下的那些柱子因为比栈顶更高仍然有资格等待属于它们自己的右墙所以暂时不弹。这就是单调栈最核心的一句话我后面还会反复回到它上面单调栈维护的是一段“还没有找到右边界”的候选柱子序列。3. 代码逐行拆解一次 pop 究竟在算什么先把完整代码贴出来用的是 Python。class Solution: def trap(self, height: List[int]) - int: n len(height) if n 3: return 0 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] w i - left - 1 h min(height[left], height[i]) - height[top] ans w * h stack.append(i) return ans这个写法有一个很阴间的点我第一次看题解的时候卡了半小时为什么每次弹出只结算一层水而不是直接把整个凹槽的水量一次性算完3.1 分层结算水不是“一坑一算”而是“一层一算”假设当前遍历到柱子 i高度比栈顶柱子 top 更高。这时候top 右侧第一个比它高的柱子就是 i而 top 左侧第一个比它高的柱子是 top 出栈之后的新栈顶 left。left、top、i 这三根柱子围成了一个凹槽看起来直接算宽度乘高度就行。但问题来了top 不一定真的是这个凹槽的最低点。凹槽真正的底部可能是 left 和 i 之间的某个更矮的柱子可能甚至在最开始就已经被弹出去了。那怎么办答案就是分层。每次只结算以 top 的高度为“地板”、以 left 和 i 中较矮者为“天花板”的这一层水宽度 w i - left - 1也就是 left 和 i 之间隔了多少根柱子高度 h min(height[left], height[i]) - height[top]这一层的净高。h 为什么不是 min(height[left], height[i]) 本身因为 top 以下的部分已经由更早的弹出操作结算过了。每一层弹出结算的都是“新露出来的那一段”这样一层层叠加上去最终就拼出了完整的储水量。3.2 完整模拟 height [4, 2, 0, 3, 2, 5]光说理论容易飘我手把手走一遍这个例子。这也是 LeetCode-42 的示例 2预期输出是 9。一开始栈为空。i0高度4栈空直接入栈。栈内[0]i1高度2不大于栈顶高度4入栈。栈内[0, 1]i2高度0不大于栈顶高度2入栈。栈内[0, 1, 2]i3高度3大于栈顶高度0进入 while弹出 top2高度0此时栈不为空left1高度2。w 3 - 1 - 1 1h min(2, 3) - 0 2ans 2。继续比较高度3仍然大于新栈顶1高度2弹出 top1此时栈不为空left0高度4。w 3 - 0 - 1 2h min(4, 3) - 2 1ans 2累计 ans4。继续比较高度3不比栈顶0高度4大while 停止。入栈 i3。栈内[0, 3]i4高度2不大于栈顶高度3入栈。栈内[0, 3, 4]i5高度5大于栈顶高度2进入 while弹出 top4高度2栈不为空left3高度3。w 5 - 3 - 1 1h min(3, 5) - 2 1ans 1累计 ans5。继续比较高度5大于新栈顶3高度3弹出 top3栈不为空left0高度4。w 5 - 0 - 1 4h min(4, 5) - 3 1ans 4累计 ans9。继续比较高度5不比栈顶0高度4大while 停止。入栈 i5。栈内[0, 5]最终 ans 9和预期一致。这个模拟过程我建议你自己在纸上画一遍尤其是 i3 那一步的两层结算第一层是左边高度2、右边高度3围住的底部0那层第二层是左边高度4、右边高度3围住的高度2那层。两次结算分别对应了同一个凹槽里的不同高度段这就是“分层”二字的直观体现。4. 三个最容易踩的坑空栈、下标、边界条件代码短短十几行但我在实际刷题和带人复盘时发现新手基本都栽在下面三件事上。每一个我都踩过或者说看别人踩过无数次。4.1 弹出 top 后栈为空必须立刻 break这是最经典的一个坑。while 条件只判断了 height[i] 大于栈顶高度但弹出之后栈可能变空。栈空了意味着什么意味着当前柱子 i 的左边没有任何柱子比它高了也就是说 left 根本不存在。左边没有更高的墙水就存不住这一轮结算没有任何意义。如果不 break直接去取 stack[-1]就会报错或拿到一个不存在的下标。即使你侥幸没报错算出来的水量也是负的或者错的。所以标准写法里弹出后第一步就是判断 if not stack: break这既是为了安全也是逻辑上必要的——没有左墙就没有凹槽。4.2 栈里存的是下标不是高度初学的时候很容易写成 stack.append(height[i])直接存高度值。真这么写了你会发现计算 w 的时候根本拿不到 left 的位置宽度算不出来。单调栈的通用约定是存下标原因有两个第一宽度 w 必须由下标的差值计算第二通过下标可以同时拿到高度值 height[stack[-1]]信息不丢失。我们平时说的“栈顶高度”其实精确说法是“栈顶下标对应的高度”。这个细节看起来不值一提但它直接关系到你能不能套用单调栈模板解决其他题。比如 LeetCode-84 柱状图中最大的矩形同样存下标但计算的是矩形面积需要高度和宽度同时参与只存高度值就完全没法做。4.3 n 小于 3 时直接返回 0至少需要三根柱子才能形成凹槽这是物理常识但写代码时容易漏。如果没有这个提前判断代码也有可能跑出一个 0但多一层防御总是好的而且面试时主动说出“少于三根柱子不可能接水”是一个体现边界意识的小加分点。另外补充一个我自己的习惯在写单调栈的时候我会在注释里写上“栈内从底到顶严格递减/递增”防止自己写着写着搞反方向。这个注释在 LeetCode 编辑器里有提醒作用尤其在面试手写代码时能帮你稳住思路。5. 为什么每个元素只进出栈一次复杂度分析要说得出单调栈的时间复杂度是 O(n)这一点几乎所有题解都会写但很多人只是背结论。面试官如果追问“while 里面不是可能跑很多次吗你怎么保证线性”卡壳的人不在少数。关键在于虽然 while 循环看起来是嵌套在 for 循环里的但每个元素被压入栈只有一次被弹出也只有一次。弹出一个元素的前提是它之前已经被压入过。所以整个算法过程中所有元素的总弹出次数不会超过 n。while 里所有的迭代次数加起来是 O(n)加上 for 循环本身的 n 次整体就是 O(n)。把话说得再直白一点面试官担心的“退化到 O(n^2)”在单调栈里不会发生因为不存在一个元素被反复弹出多次的情况。它不像暴力法那样每个柱子都要回头向左扫描找左边更高的墙。单调栈的做法是每个柱子右边出现更高墙的那一刻过去积压的所有“未结算”柱子按顺序统一结算一次每个柱子恰好轮到一次。空间复杂度方面栈最多同时存 n 个下标所以是 O(n)。如果你想跟面试官聊优化可以顺势引出双指针做法那个能做到 O(1) 空间。但我的个人建议是不要为了秀优化而跳过单调栈——单调栈的思路对理解边界问题的价值比那一点空间节省重要得多。6. 学会一道题吃透一类题单调栈的扩展练习路线接雨水做完之后别急着划走。我自己的体会是单调栈这类题必须“连成串”刷单做一道容易只是记住了代码连刷几道才能真正理解那个筛子的工作方式。下面这条练习路线是我实际走过之后觉得效率最高的。6.1 先做基础题LeetCode-496 下一个更大元素 I这道题是单调栈最纯粹的形态。给你两个数组问第一个数组里每个元素在第二个数组中右边第一个比它大的数是多少。没有复杂的水量计算只需要用递减栈扫描一遍把每个元素的“下一个更大元素”记录到哈希表里。做完这道题你会对“弹出即意味着找到了答案”有直观感受。接雨水里那个 while 循环本质上就是在反复执行“栈顶找到了右侧第一个更高元素”这个动作只是多了一步水量结算。6.2 再攻变体LeetCode-84 柱状图中最大的矩形这道题和接雨水常常被拿来对比。接雨水找的是“凹槽”84 题找的是“以当前柱子为高的最大矩形”。它同样用单调栈但边界条件完全反过来需要加哨兵柱处理首尾边界。刷完 84 题你会意识到单调栈的难点根本不在于模板而在于“什么时候结算、结算什么”。同样是 pop 一个元素接雨水结算的是水量84 题结算的是面积pop 的触发条件也从“遇到更高的墙”变成了“遇到更矮的墙”。这个对比能帮你把单调栈从死记硬背中解放出来。6.3 最后补三道应用型题目如果还有余力我建议按顺序做下面三道LeetCode-739 每日温度标准单调栈找右侧第一个更高温度出现在几天后。这道题能帮你强化“栈里存下标”的直觉。LeetCode-901 股票价格跨度把单调栈用在连续区间计数上跨度计算和接雨水的宽度计算思路很像。LeetCode-402 移掉 K 位数字单调栈加贪心长度固定时让高位数尽量小。这道题会打破“单调栈只能处理大小关系”的刻板印象。这几道题全部做完你对单调栈的理解会从“背模板”变成“基于需求设计栈策略”再遇到新题就能条件反射地判断该用哪种栈、什么时候弹出、弹出时算什么。7. 如果面试官让你讲思路一段可以背下来的话术最后分享一个很实际的场景。面试时你写完代码面试官大概率会问“讲讲你的思路。”很多人这时候开始对着代码一行行念这是大忌。真正好的讲解是先讲宏观再讲微观。我建议你按这个顺序说“我用了一个单调递减栈栈里存的是柱子下标从栈底到栈顶对应的高度严格递减。这等价于维护了一串还没找到右侧更高墙的柱子。当我遍历到一根新柱子时如果它比栈顶高说明栈顶那根柱子找到了右边界我可以把它弹出来结算水量。结算时新的栈顶就是它左边最近的更高的墙当前柱子是右边最近的更高的墙用这两堵墙的较矮高度减去被弹出柱子的高度作为这一层水的深度宽度就是两堵墙之间的下标距离。循环弹出直到当前柱子不再比栈顶高然后把当前下标入栈。因为每个元素只会入栈和出栈一次总复杂度是 O(n)。”这段话的妙处在于没有提任何代码细节但把数据结构递减栈、触发条件当前高于栈顶、结算内容宽度、水深、复杂度结论全部讲清楚了。面试官听完就知道你不是背的。我个人刷题这么多年接雨水是我反复回来重做次数最多的题之一。每次重做都能发现自己对单调栈的理解又深了一点。从最初照着题解抄到能自己推导出分层结算再到能跟别人讲清楚每一行代码的理由这个过程本身就值回票价。希望你也能在 Day 171 这天把这道题彻底吃透。