吃透单调栈：每日温度与柱状图最大矩形的通用解法

刷算法题遇到瓶颈期往往不是题刷得不够多而是某些核心数据结构没吃透。单调栈就是这样一种会者不难、难者不会的技巧。我最初在做LeetCode的每日温度和柱状图中最大的矩形这两道题时第一反应都是暴力解法结果一个超时一个逻辑混乱。后来把单调栈模板理解透了再看这两道题发现它们本质上是同一个套路用一个单调栈维护还没确认答案的元素当新元素满足条件时结算栈顶元素的答案。这篇文章就围绕这两道题把单调栈的原理、推导过程、代码模板和避坑经验一次讲清楚。适合准备算法面试、刷题到中等难度卡壳、或者想系统搞懂单调栈的读者。1. 先搞清楚单调栈到底干了一件什么事1.1 从一个找下一个更大元素的小需求说起假设有一个数组 [2, 1, 4, 3]希望求出每个元素右边第一个比它大的元素2 对应 41 对应 44 对应无3 对应无。最直接的思路是两层循环对每个元素往右扫描。但假如数组长度是 10^5最坏情况下比如严格递减的数组每个元素都要扫到末尾总操作量是 n²直接超时。这里其实不用先上下一个更大元素的模板它和单调栈的关系非常直接。单调栈方案是从左往右遍历数组维护一个栈让栈内元素的值从栈底到栈顶保持单调。遍历到新元素时不断弹出那些已经被新元素击败的栈顶元素。什么叫击败如果新元素比栈顶元素大那么就找到了栈顶元素右边第一个更大的元素栈顶元素的答案确定了可以出栈。说白了单调栈就是把尚未确定答案的元素暂存在栈里等待一个合适的时机一把结算而不是让每个元素都向后盲目扫描。这个思想在每日温度里表现为等更高的温度在柱状图最大矩形里表现为等更矮的柱子。理解了这个后面两道题只是换了个皮。1.2 单调递增栈与单调递减栈的选型规律栈分两种形态初学者最常见的困惑就是什么时候用递增什么时候用递减。单调递增栈从栈底到栈顶元素值严格递增。适合解决找左边或右边第一个比自己小的元素。单调递减栈从栈底到栈顶元素值严格递减。适合解决找左边或右边第一个比自己大的元素。这里的单调性说的是栈内元素的值不是下标。为什么找更大的要用递减栈因为新元素到来时如果它比栈顶元素更大说明栈顶右边第一个更大的元素出现了可以弹出结算如果它更小说明栈里所有比它大的元素都没等到更大的而它自己还有机会所以直接入栈。反过来找更小要用递增栈。用一个生活化类比栈像一个按身高从高到矮排好的队队首最高。新来一个更高的人时就把队首的人领走队首的紧邻第一个比自己高的人出现了。所以每道题先问自己要找右边第一个更大的还是更小的答案直接决定栈的形态。我见过不少人栽在这上面把两个方向记反代码跑出来完全不对。1.3 复杂度为什么能降到O(n)单调栈最关键的性质是每个元素最多入栈一次、出栈一次。第一次看 while 循环时容易担心会不会某一步一口气弹很多个总体还是平方不会。被弹出去的元素不会再回来所以整个遍历过程总的弹出次数不超过 n每个元素入栈一次整体复杂度 O(n)。空间复杂度也好理解最坏情况下栈里会存下所有元素。比如一个严格递增的数组用单调递增栈时每个新元素都比栈顶大全都入栈空间 O(n)。这个复杂度收益在 n10^5 时差别巨大。O(n²) 是 10^10 次操作基本跑不起来O(n) 是 10^5 次操作毫秒级返回。算法题里一旦发现暴力解法涉及每个元素都向后找一次边界第一反应就该是能不能用单调栈把重复扫描省掉。2. 每日温度等一个更高的温度把等待时间算出来2.1 题目语义和暴力解法的局限题目本身不复杂给定整数数组 temperatures 表示每天气温返回一个数组 answer其中 answer[i] 表示在第 i 天之后需要等几天才出现更高的温度。如果后面没有更高的温度对应值为 0。例如 [73, 74, 75, 71, 69, 72, 76, 73]返回 [1, 1, 4, 2, 1, 1, 0, 0]。暴力解法就是两层循环外层固定某一天 i内层从 i1 开始往后找第一个 temperatures[j] temperatures[i]记录 j-i。这个想法很直觉但内层扫描存在大量重复劳动。举个例子第 2 天温度是 75它需要等到第 6 天的 76于是它会把第 3、4、5 天全部遍历一次。而第 0 天的 73 要等第 1 天的 74第 1 天的 74 要等第 2 天的 75……每次都在向后扫描不同长度的区间加起来就是 O(n²)。当数据量上来之后超时几乎是必然的。2.2 从暴力到单调栈出栈时才是结算时机换一个角度想与其每个元素都向后扫描不如让每个元素挂在栈里等第一个能让它出栈的元素出现。具体做法是维护一个栈保存的是下标但栈内下标对应的温度从栈底到栈顶是严格递减的。遍历每一天 i只要栈非空且 temperatures[i] 大于栈顶下标对应的温度就说明栈顶那天等到了第一个更高的温度弹出栈顶下标 idx记录 ans[idx] i - idx重复弹出直到当前温度不大于栈顶温度把当前下标 i 入栈。为什么这样可行因为栈内所有元素的温度是递减的越靠栈顶温度越低说明它们都在等待一个比自己高的温度。新来的元素一旦比栈顶温度高栈顶的等待结束同时新元素也可能比栈内其他元素高所以要一直弹出直到遇到比自己高或相等的栈顶元素。至于遇到相等不弹出因为题目要求的是更高的温度相等不算继续等。用 [73, 74, 75, 71, 69, 72, 76, 73] 推演一遍步骤当前温度弹出下标结算结果入栈后的栈i073无无[0]i1740ans[0]1[1]i2751ans[1]1[2]i371无无[2,3]i469无无[2,3,4]i5724ans[4]1[2,3]i5723ans[3]2[2]i6765ans[5]1[2]i6762ans[2]4[6]i773无无[6,7]十个步骤看完整个过程非常清晰。栈里最后剩下下标 6温度 76和下标 7温度 73说明它们后面没有更高的温度ans 保持默认值 0 即可。也可以从右往左遍历维护一个栈从右往左时栈底到栈顶递增遇到新元素时把栈中比它小的元素全部弹出栈顶剩余元素就是右边第一个比它大的下标。两种方向都行但很多同学更习惯从左往右版本面试时选一种练熟就好。我个人推荐从左往右因为它更贴近延迟结算的直观理解。2.3 代码实现与三个容易翻车的小细节def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx stack.append(i) return ans代码短但细节不少。第一栈里存的是下标而不是值。因为要算天数差存值的话还得回查数组多一环不如直接存下标。第二用 while 而不是 if。一个高温天可能一次结算多个栈内元素比如上表的 76 一口气结算了下标 5 和下标 2 两个等待者只弹一个就丢了信息。第三ans 初始化为全 0。最后留在栈里的元素不用额外处理天然就是 0省掉了一次清理逻辑。翻车高发点也集中在这里有人会把 while 写成 if结果高温只结算栈顶一个元素有人会把 temperatures[stack[-1]] 写成 stack[-1] 本身的大小下标和值混用直接得到错误答案。这些坑我在初学时都踩过手动推一遍才能彻底改掉。3. 柱状图最大矩形面积每个柱子都适合当最低点3.1 为什么枚举区间不是好方案题目要求给定一个非负整数数组 heights每个值代表一个柱子的高度柱子的宽度都是 1求这些柱子能勾勒出的矩形中面积最大的是多少。经典例子里heights [2, 1, 5, 6, 2, 3]正确答案是 10也就是第 2 到第 4 根柱子高度 5 和 6之间以高度 5 为矩形高的那块面积 5×210。最暴力的思路是枚举所有可能的左右边界区间对每个区间找到区间内的最小高度用最小高度乘以区间宽度。这个做法的问题很明显枚举区间本身是 O(n²)在每个区间里再找最小值不做预处理就是 O(n³)。即便做了预处理优化n 到 10^5 之后依然不可行。另一个常见思路是枚举高度把每根柱子当作矩形的高度然后向左右扩展扩展到高度小于当前柱子的地方为止。这个想法是对的但难点在于向左右扩展到哪里为止需要高效求解。如果能提前知道每个柱子左边第一个更矮的下标和右边第一个更矮的下标面积就很容易算。3.2 左边界右边界用单调栈一次扫描搞定记当前柱子下标为 i高度为 h[i]。它能作为高的矩形左边界应该是左边第一个高度小于 h[i] 的柱子下标 left右边界应该是右边第一个高度小于 h[i] 的柱子下标 right。左右边界开区间内的柱子高度都不小于 h[i]所以矩形宽度为 right - left - 1面积为 h[i] * (right - left - 1)。这里有一个非常经典的细节左右边界处理相等高度时到底要不要算进去。如果一个矩形的高度是 h那遇到和 h 相等的高度继续扩展也不会让矩形变高但会让面积更大所以理论上遇到小于 h的才停没有问题。问题在于如果两个等高的柱子相隔若干根它们在分别计算时会把同一块宽度重复计算。但因为面积相等或较小取最大值时不影响最终答案。因此实现里常见一个方向用严格小于另一个方向也用严格小于重复计算只会多花一点常数时间不会得到错误结果想避免重复就让其中一个方向遇到相等时停下。单调栈在这里的作用是同时找左右边界。从左往右遍历时维护一个栈底到栈顶递增的栈也就是栈内高度从小到大。当前柱子高度小于栈顶时说明栈顶柱子向右扩展时遇到了第一个比自己矮的柱子于是它的右边界就是当前下标 i弹出栈顶后新的栈顶就是它左边第一个比它矮的柱子。如果栈空了说明左边没有更矮的left 取 -1。为什么这里要用单调递增栈而不是递减栈因为要解决的是找更矮的柱子。按照第一节的选型规律找左边或右边第一个更小的正好是单调递增栈的主场。每次遇到一个让自己变矮的新柱子结算栈顶维护的就是栈内高度递增的状态。方向记反的话推演第二次就会卡住。3.3 完整代码与哨兵0的作用def largestRectangleArea(heights): heights.append(0) # 哨兵最后把所有柱子都弹出来结算 stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, h * width) stack.append(i) return max_area这里的关键是最后追加的哨兵 0。如果不加哨兵遍历结束后栈里还会剩下一些递增的柱子这些柱子的右边界并不存在没有触发结算。在末尾补一个高度 0 的柱子它比所有柱子都矮会强制把所有柱子弹出结算代码不用单独再写一次清理逻辑。这个技巧在很多单调栈题目里都能复用比如接雨水里也经常用类似思路。注意代码里用的是 heights[i] heights[stack[-1]]也就是右边界取第一个严格更矮的柱子而左边界取弹出后的栈顶。因为两个方向都取严格更矮等高的柱子会重复计算区域但最终面积取最大值不受影响。如果想把重复计算也省掉可以把比较条件改成 在右边遇到相等就停下来左边界那边自然不重复。修改 heights 数组本身会改变原数据。如果不想让函数产生副作用在函数开头写 heights heights [0] 复制一份即可。这个细节在面试里被问过不算大问题但能体现你对函数副作用是否敏感。3.4 手动推演heights [2, 1, 5, 6, 2, 3]我用这个例子带你过一遍核心过程。先复制一份 heights 并在末尾加 0得到 [2, 1, 5, 6, 2, 3, 0]。i0栈空入栈 0栈为 [0]i1高度112弹出下标0h2栈空所以 left-1宽度1-(-1)-11面积2入栈1栈为 [1]i2高度551入栈栈为 [1,2]i3高度665入栈栈为 [1,2,3]i4高度226弹出3h6left2宽度4-2-11面积6继续 25弹出2h5left1宽度4-1-12面积102 不小于栈顶1的高度1停止入栈4栈为 [1,4]i5高度332入栈栈为 [1,4,5]i6高度003弹出5h3left4宽度6-4-11面积302弹出4h2left1宽度6-1-14面积801弹出1h1栈空所以 left-1宽度6面积6结束。最大面积为 10与题目答案一致。手动推演这一步特别重要很多人的代码写对了但对结算环节理解不深推一遍才知道每一步到底在算什么弹出栈顶柱子时是它的右边界刚出现宽度用它和左边界之间的距离算出来。4. 把两道题看成同一道题延迟结算的窗口4.1 统一的抽象过程两道题放到一起看其实是同一个流程遍历数组时把还没出结果的元素放进栈里新元素满足某个结算条件时把栈顶元素弹出并计算它的答案处理完弹栈后再把新元素入栈。在每日温度里结算条件是新温度比栈顶温度更高在柱状图矩形里结算条件是新柱子高度比栈顶高度更矮。表面上一个找更大、一个找更小实际都是新元素触发了栈顶元素的边界确认。单调栈最隐蔽的价值在于它把向后找边界变成了向前结算让每个元素只被处理两遍。这个思想可以抽象成三段伪代码for 每个元素 e: while 栈非空 and 当前元素和栈顶元素满足结算条件: 弹出栈顶 t 根据 t 和其他信息计算答案 当前元素入栈每次写单调栈题我都先把这个框架默背一遍再根据题目往里填内容。填的时候只需要回答两个问题结算条件是什么弹出时用什么公式算答案这两个问题想清楚代码基本就出来了。4.2 识别单调栈题的三个特征第一个特征暴力解是 O(n²) 的区间或边界扫描。比如下一个更大元素每日温度最大矩形都符合。第二个特征答案与左右边界或跨度强相关。等待天数本质是下标差矩形面积本质是宽度乘高度股票跨度本质是边界距离。第三个特征数据规模不允许 O(n²)。LeetCode 中 n 到 10^5 的数量级基本就是暗示用 O(n) 或 O(n log n) 的做法。同时提醒一下并不是所有区间题都适合单调栈。滑动窗口最大值这种固定窗口长度的题适合用单调队列而不是单调栈。两者的区分在于队列先进先出适合窗口不断平移栈后进先出适合最近一个未结算元素的场景。把单调栈和单调队列混用是很多人踩过的大坑我也曾在一个滑动窗口题里硬套单调栈最后越写越乱。4.3 高频变形与扩展题掌握了核心模板之后很多题只是换了个壳。常见变形包括下一个更大元素 I / II直接套单调递减栈。循环数组的处理方式是把数组遍历两遍用下标取模 % n 模拟循环但要注意同一个元素最多只能入栈一次否则会无限循环。股票价格跨度输入是流式的但仍然可以用单调栈维护某价格之前的连续天数本质上就是找左边第一个更高的价格用栈存跨度的累计值。接雨水思路是凹槽两侧较矮的边决定积水高度用单调递减栈在遇到更高的右边界时结算凹槽每次弹出时计算可以接住的水量。最大宽度坡维护一个递减栈存候选左端点再从右往左扫描。这个变形比前两个更难想到因为它不是相邻元素直接结算而是需要二次扫描配合建议专门练一练。柱状图中最大的矩形是很多面积类问题的基础比如全 1 矩阵的最大矩形就是在每一行上套用柱状图的做法。如果把这些题按找更大 / 找更小分个类会发现选型规律非常稳定找更大元素就维护递减栈找更小元素就维护递增栈。把这两条刻进脑子里选型环节就不会犹豫了。5. 刷完这两个题后我的调试方法和避坑清单5.1 调试第一招手推一张栈变化表我自己写完单调栈代码如果答案错误第一件事不是反复读代码而是拿一组小样本数据在纸上把每一步的栈状态写出来。建议每步都记录四样东西当前下标、当前值、弹出的下标和值、入栈后的栈内容。写完之后和代码执行结果对比很快就能定位是哪个分支逻辑错了。比如在每日温度里如果你推演到 i5 温度 72 时发现本该连弹两个等待元素却只弹了一个基本就是 while 写成了 if。在柱状图矩形里如果推演到最后发现栈里还残留元素一定是你忘了加哨兵 0或者右边界计算时把 left 取错了。我自己还会在代码里临时加 print 输出栈状态调完再删掉。虽然面试时不能这么干但平时刷题调试效率能高不少。等代码通过之后再把这组 print 删掉提交干净版本。5.2 我把常见错误列成了一张自查清单遍历时比较的是栈顶下标还是栈顶元素的值取错的话结果会非常离谱。一个稳妥写法是先用 idx stack[-1] 拿出下标再比较 heights[idx]避免下标和值混用。栈为空时访问 stack[-1]while 条件的顺序必须写 stack and ...Python 里短路求值能避免空栈异常其他语言里也要先判空再取栈顶。答案数组的默认值不能乱设每日温度默认 0 没问题矩形面积初始 max 设 0 也没问题但有些题可能要求返回下标而不是距离默认值要看题目语义再定。忘记处理循环数组的下标转换如果对 2n 数组遍历写入答案时要限制在原始下标范围否则数组越界或覆盖错误位置。等号方向 和 、 和 的选择要对照题目语义。严格大于才算更高温度时用 严格小于才算右边界时用 如果题目说大于等于或小于等于就把等号加上。这个细节决定了很多 WA 到底是逻辑错还是条件边界错。5.3 面试和日常刷题里的小技巧如果面试遇到单调栈题我习惯先给一个暴力解法再说优化。口头表达时可以这样说每个元素向后找一次最坏 O(n²)但如果维护一个栈让每个元素只入栈一次、出栈一次就能做到 O(n)。这样既展示了思路演进也让面试官看到你不是在背模板。写代码前先在白板上用三五个输入推演一下能避免大量返工。推演时注意哪个方向是严格哪个方向是非严格这是最容易错的点。另外如果面试官问了复杂度一定要说清楚内存占用最坏情况栈里存了全部元素所以空间是 O(n)。我自己在复盘时会把这两个经典题当作模板保存但不会死记代码而是记住那个延迟结算的思想。遇到新题第一件事是把暴力思路想清楚然后问自己每个元素的边界是否由相邻大小关系决定如果是单调栈大概率能上。最后再分享一个实战技巧我遇到单调栈题目时会强制自己在代码里写注释标清什么时候弹出和弹出后计算什么。这个习惯帮我减少了一半以上的低级错误。如果你刚开始接触单调栈别急着背模板先手动把每日温度和柱状图最大矩形各推演三遍推熟之后去看下一个更大元素和接雨水会发现整个数据结构串成了一条线。等你能一眼看出这题要找左边还是右边、比大还是比小单调栈就真正变成你的武器了。