做算法题最怕遇到那种名字听着唬人、实现起来却寥寥几行的数据结构题单调栈就是典型。第一次看到“每日温度”这种题时我想着无非是拿个数组来回扫结果数据量一上来就超时。后来认真把单调栈吃透才发现它解决的是一整类问题在数组里快速找“下一个更大/更小元素”而“柱状统计图最大矩形面积”是这类思路里最考验细节的一道题。这篇文章就从这两个经典场景入手把单调栈的原理、代码、边界情况和调试心得一次说清楚适合正在刷题准备面试的同学也适合工作中需要做区间统计、温度预测这类小需求的工程师。1. 单调栈的核心思想从暴力到有序的思维转变1.1 单调栈到底是什么很多人一看到“单调栈”三个字就开始紧张觉得它是什么高级数据结构。其实它就是在普通栈的基础上加了一条约束栈内元素从栈底到栈顶始终保持单调递增或者单调递减。就这么简单。你可以把它理解成一条有序的队列只不过这个队列只允许从一端进出。每次往栈里压入新元素时如果破坏了单调性就把栈顶元素弹出去直到重新满足单调条件为止。为什么会有这种数据结构答案在于很多问题天生就要求我们“找最近关系”。比如你在排队买东西想知道每个人后面第一个比自己高的人是谁如果暴力做每个人都要往后看一遍整体就是 O(n^2)。但如果用单调栈每个人最多进栈出栈一次总复杂度能做到 O(n)。单调栈存在的意义本质上是利用了“栈顶永远是最新数据”这个特性结合单调性做到了对历史信息的快速整理和淘汰。1.2 单调栈的两种形态与选择依据单调栈分两种单调递增栈和单调递减栈。名字容易把人绕晕我教你一个不会记错的办法如果栈内从栈底到栈顶是递增的那它就是单调递增栈。这种栈适合用来找“左边或右边第一个更小的元素”。如果栈内从栈底到栈顶是递减的那它就是单调递减栈。这种栈适合用来找“左边或右边第一个更大的元素”。为什么因为单调递增栈里栈顶是当前区间里最大的元素当你遇到一个新元素比栈顶小的时候栈顶就被“卡住”了——新元素就是它右边第一个更小值。同理单调递减栈里栈顶是最小的新元素比栈顶大时栈顶的“右边界”就确定了。提示真正写代码时很多人会纠结到底该用递增还是递减。我的经验是先确定题目要什么“关系”如果题目问“下一个更大”那就维护递减栈如果问“下一个更小”就维护递增栈。记住这个对应关系比死背栈类型要可靠得多。1.3 为什么每个元素只需要处理一次让很多初学者想不通的是单调栈凭什么能做到 O(n)暴力解法明显需要 O(n^2) 的遍历单调栈为什么就能保证每个元素只进出一次关键在于“淘汰”二字。用一个生活案例来解释假设有一排人你要满足“每个人向右看找到第一个比自己高的人”。如果第一个人很高后面连续来了好几个都不如他高那这些人会被依次压入一个递减栈。当终于来了一个比他高的人时这个高个子不光解决了第一个人还会顺带把栈里所有比他矮的人都解决了因为对他们来说这个高个子就是右边第一个更高的。而那些被弹出的元素再也不会被用到因为它们已经得到了答案留着只会干扰后续判断。这就是单调栈高效的根本原因已经答案明确的元素会立刻出栈留在栈里的永远是需要继续等待右边界或左边界的候选元素。理解了这一点你就能明白单调栈的空间复杂度为什么是 O(n)以及它为什么能把嵌套的比较拍平成一个线性扫描。2. 每日温度三步从暴力到单调栈2.1 题目本质与暴力瓶颈“每日温度”这个题的业务背景很简单给你未来几天的气温数组要你算出每一天要等多少天才能等到一个更高的气温如果后面没有更高气温就填 0。比如气温是 [73, 74, 75, 71, 69, 72, 76, 73]对应的结果应该是 [1, 1, 4, 2, 1, 1, 0, 0]。第 0 天温度 73第 1 天 74 就比它高所以等 1 天第 2 天温度 75要到第 6 天的 76 才更高中间隔了 4 天最后两天后面没有更高温度结果都是 0。暴力的思路很直接两层循环。外层固定某个位置 i内层从 i1 开始往后扫描直到找到第一个比它大的值记录下标差。这个方法代码简单但一旦数组长度到了 10^5 级别最坏情况下几乎每次都要扫到末尾O(n^2) 的复杂度直接让程序超时。那为什么暴力会傻因为它没有利用已经扫描过的信息。比如第 2 天的 75 在等待答案时已经扫过了 71、69、72这些信息在暴力法里用完之后就被丢弃了等到第 3 天 71 再往后扫描时又要重新扫描 69、72。这显然是在重复劳动。2.2 单调栈写法与逐行拆解单调栈解法在思路上完全反转不搞两层循环而是从左到右遍历一次用栈保存“还没有等到答案”的下标。这里我需要维护一个递减栈也就是栈底到栈顶温度递减。为什么因为我们要找的是“下一个更高的温度”栈顶元素是最近一个还没等到答案的下标。如果当前温度比栈顶下标对应的温度高那当前这一天就是它的答案。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i, t in enumerate(temperatures): # 当前温度比栈顶温度高说明栈顶元素等到了答案 while stack and t temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx # 当前下标压入栈继续等待右边的更高温度 stack.append(i) return ans代码的核心逻辑只有一步循环但里面有个细节值得单独说为什么 while 循环里要反复弹出因为当前元素可能比栈里多个元素的温度都高比如温度序列 [70, 71, 72]当遍历到 72 时栈里先压着 70 的下标再压着 71 的下标。当前值 72 比栈顶 71 对应的温度高弹出 71 并记录答案弹出后新栈顶是 7072 也比它高继续弹出并记录答案。这样一次遍历就把前面等待的所有小弟的答案都结算了。2.3 为什么栈里存下标而不是温度值新手最容易踩的坑就是把温度值直接压进栈。你要想明白ans[idx] i - idx 需要的是“天数差”也就是两个下标之间的距离。如果栈里只存温度值确实能判断当前温度是不是比它高但算不出过了几天。所以正确答案永远是存下标需要温度时用下标去原数组里取。这也是单调栈题的通用约定栈中保存下标原数组负责提供值。把这两个信息分开管代码的灵活性会高很多。比如日后再遇到需要同时比较“值”和“位置”的题你都只要在同一套框架里做小改动就行。2.4 为什么最后栈里剩的是什么遍历结束后栈里可能还有残留的下标。这些下标代表什么代表它们从入栈到现在始终没有遇到比自己温度更高的元素所以对应的答案保持初始值 0。这里有个小细节初始化 ans 为全 0 时栈里剩余元素就不需要特殊处理直接忽略即可。这其实是单调栈题里很常见的技巧——先把答案预设为“没有结果时的情况”然后只在确定答案时才更新。我实际做题时一开始很怕“栈里还有元素”这种场景总觉得要清理一下才算完。但仔细一想这些元素本来就没有答案保持默认值反而是最自然的状态。3. 柱状图最大矩形单调栈的进阶考验3.1 问题分析与暴力瓶颈如果说每日温度是单调栈的入门题那“柱状图中最大的矩形”就是把单调栈推向进阶的经典题。题目描述也很直白给定一组柱子的高度找出一根连续的柱状区域内能勾勒出的最大矩形面积。比如柱子高度 [2, 1, 5, 6, 2, 3]直觉上会想到高度 5 和高度 6 相邻能构成宽 2 高 5 的矩形面积是 10。但真正的最大面积其实是高度 5 和 6 加上后面高度 2 共同形成一个宽 3 高 2 的矩形吗不对高 2 的矩形只有 2 宽面积 4。再想想以 1 为高度的矩形宽度可以横跨整个数组面积 6以 2 为高度的矩形从下标 0 到下标 4宽度 5面积 10等等。正确的最大面积是 10由下标 2 和 3 的两根柱子分别作为左边界算出来。这个问题的本质是对于每一根柱子如果把它当作矩形的高那矩形的宽度是由什么决定的是由左右两边第一个比它矮的柱子决定的。比如高度为 5 的柱子在下标 2左边第一个比它矮的是下标 1 的高度 1右边第一个比它矮的是下标 4 的高度 2所以宽度是 4 - 1 - 1 2面积就是 5 * 2 10。暴力的做法有两层思路一是固定左边界枚举右边界算最小高度乘宽度二是固定某根柱子向左向右分别扩展找边界。两个都是 O(n^2)在 n 大时同样崩溃。问题核心和每日温度一模一样怎么样快速找到每根柱子“左右第一个比它矮的下标”。3.2 单调栈加哨兵的完整写法这里的单调栈要用递增栈因为我们要找的是“第一个更矮”的元素。从左向右遍历时如果当前柱子高度小于栈顶柱子的高度那栈顶柱子就找到了它的右边界而栈内紧挨着它的下一根柱子就是它的左边界。一个常见的痛点是边界条件处理当栈为空时没有左边界当遍历结束后栈里剩余的柱子还没找到右边界。为了不写一堆 if 判断有一个经典技巧在数组首尾各插入一根高度为 0 的哨兵柱子。首部的 0 保证了栈永远不为空因为第一个元素 0 永远在栈底可以作为任何柱子的左边界。尾部的 0 保证遍历到它时所有还没找到右边界的柱子都会被弹出结算因为它比任何正数高度都矮。def largestRectangleArea(heights): # 首尾加哨兵简化边界处理 heights [0] heights [0] stack [] max_area 0 for i in range(len(heights)): # 当前高度小于栈顶高度时栈顶柱子的右边界确定 while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] # 弹出的柱子高度作为矩形的高 # 此时新的栈顶就是左边界i 是右边界 w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area写下来只有十来行但每一行都有讲究。我的建议是不要直接背代码先自己手动跑一遍小样例把 pop 和 push 的过程画出来才能真正理解宽度为什么是 i - stack[-1] - 1。3.3 手动模拟一次遍历全过程拿 [2, 1, 5, 6, 2, 3] 加哨兵后变成 [0, 2, 1, 5, 6, 2, 3, 0]我们逐步看i0高度 0栈空压入 0。i1高度 2栈顶 0 2不弹出压入 1。现在栈内是 [0, 1]。i2高度 1栈顶 2 1弹出 1。h2左边界是新的栈顶 0右边界是 i2宽度 2 - 0 - 1 1面积 2。继续比较栈顶 0 1停止弹出。压入 2。栈内 [0, 2]。i3高度 5栈顶 1 5压入 3。i4高度 6栈顶 5 6压入 4。i5高度 2栈顶 6 2弹出 4。h6左边界是新的栈顶 3右边界是 i5宽度 5 - 3 - 1 1面积 6。继续比较栈顶高度 5 2弹出 3。h5左边界是栈顶 2右边界 i5宽度 5 - 2 - 1 2面积 10。继续比较栈顶高度 1 2停止。压入 5。栈内 [0, 2, 5]。i6高度 3压入 6。i7高度 0栈顶 3 0弹出 6。h3左边界是栈顶 5右边界 i7宽度 7 - 5 - 1 1面积 3。继续弹出 5h2左边界是栈顶 2宽度7-2-14面积 8。继续弹出 2h1左边界是栈顶 0宽度7-0-16面积 6。最后栈内只剩 [0]循环结束。手动跑完一遍你就能看到每一根柱子作为矩形高时它的左右边界是如何通过一次出栈瞬间确定的。最大面积 10 在下标 4 那一轮记录了下来实际对应高度 5 和 6 并排的矩形。这就是单调栈的妙处一次遍历所有柱子的“可扩展宽度”都被自动结算了。3.4 关于“小于”和“小于等于”的一点辨析有些朋友在写这个题时会把 while 里的比较条件改成 heights[i] heights[stack[-1]]。这两种写法在某些题里会得到不同结果但在柱状图最大矩形这里结果是等价的。区别在于相等高度的柱子处理时机不同。用 时相等高度会留在栈里继续等待直到遇到更矮的柱子才被统一弹出这样宽度会包含多个相等高度柱子面积计算仍正确。用 时相等元素会提前弹出宽度计算时会把相等的柱子算作右侧边界但由于高度相同计算结果也一样。我个人习惯用 因为语义更贴近“严格第一个更矮”。但如果在接雨水这种题里用 或 就会影响重叠部分的处理所以刷题时一定看清楚题目是在求“严格更小”还是“可以相等”。这个细节就是区分入门和进阶的试金石。4. 单调栈通用套路与变形题识别4.1 两套通用模板先存下来单调栈题做多了就会发现套路极其固定。我把最常用的两套模板写在这里建议收藏。找下一个更大元素维护递减栈。def nextGreater(nums): n len(nums) res [-1] * n stack [] for i in range(n): while stack and nums[i] nums[stack[-1]]: res[stack.pop()] i stack.append(i) return res找下一个更小元素维护递增栈。def nextSmaller(nums): n len(nums) res [-1] * n stack [] for i in range(n): while stack and nums[i] nums[stack[-1]]: res[stack.pop()] i stack.append(i) return res这两个模板唯一的区别就是比较符号。把这两种背熟之后看任何单调栈题第一反应都是这题是不是在找“左右第一个更大/更小”如果是就往模板上套。4.2 如何识别一道题该用单调栈我总结了三个特征基本可以覆盖大部分情况需求是“找某个元素最近一侧的更大/更小值”或者“由这个更值决定边界/区间”。暴力做法是 O(n^2)而题目数据范围到了 10^5 以上需要线性解法。题目里出现“温度、海拔、柱子、价格跨度、视野遮挡、区间面积”等关键词往往背后都有单调栈的影子。拿“接雨水”举例它表面是在算水量但核心在于每个位置能存多少水取决于它左右两侧最高柱子的较小值。这虽然不是标准的“下一个更大”问题但如果你用单调递减栈维护一个海拔递减序列其实也能在遍历过程中找到左右边界。理解了下一更大 / 下一更小的套路接雨水的解法和柱状图最大矩形几乎如出一辙只是面积换成了水量方向换成了求较小值。4.3 几个值得练手的变形题下一个更大元素 I / II基本模板题第二题把数组拼成两倍长度处理循环数组还可以进一步练“取模下标”的技巧。股票价格跨度本质是求“左边连续小于等于当前值的个数”用递减栈做栈顶被弹出时顺便维护跨度。去除重复字母这题稍微绕一点需要用单调栈结合字符频次判断某个字符能不能被弹出但它让你在套路之外学会处理“全局约束”。接雨水和柱状图最大矩形高度对称强烈建议两个题放一起对比做做完你会对“左右边界”这个概念有更深的体感。我的学习路径建议是先做纯模板题再做每日温度再上柱状图最大矩形最后拿接雨水做正反对比。每做一道都要把“为什么维护递增/递减栈”用一句话讲给自己听。讲不出来的地方就是还没掌握精髓的地方。5. 实操过程中的常见坑与调试心得5.1 边界条件空栈、哨兵、相等元素在实际刷题和编码中下面几个坑我反反复复踩过提前帮大家避一避。第一空栈问题。在 while 循环里比较栈顶时栈可能是空的。如果你直接访问 stack[-1] 就会越界。所以 while 条件里必须写 stack and ...这个顺序不能反。很多人图省事写在一起结果栈空时报错调试半天才发现。第二哨兵的选取。柱状图最大矩形里加的哨兵是 0因为柱子高度都大于等于 00 肯定小于任意正数高度能作为“必然更矮”的边界。如果你遇到的问题允许负数那就得用负无穷或者单独判断不能无脑套。第三相等元素。前面提过 和 的差异这里再强调一次如果你把比较符号写反某些题比如接雨水结果就错了。排查时最先检查是不是比较方向反了。5.2 代码层面容易忽视的隐藏 bug另外一个高频 bug 是在弹出栈顶后直接拿旧栈顶当作左边界。这是错的。因为 pop 之后新的栈顶才是符合条件的左边界。比如柱状图最大矩形里弹出下标 4 后左边界是栈内剩下的下标 3而不是刚弹出的下标 4。这两者的差别就是宽度计算里到底要不要减 1错一处整个面积全部算错。还有一个容易忽略的点初始化答案时习惯性用 0 还是 -1。每日温度里答案最差是 0所以初始化为 0 没问题。但有些题比如下一个更大元素如果不存在时答案应该是 -1要记得按题目要求初始化。用模板时把 res 的默认值当成题目输出的一部分来考虑而不是只当作临时变量。5.3 徒手推演和打印辅助的排查流程真遇到 bug 时我的经验分三步第一步纸上手动模拟。拿一个小样例按代码逻辑一步步画栈的变化。只要栈的 push/pop 顺序和预期不一致问题通常出在判断条件。比如每日温度里温度相等时该不该弹出手推一遍立刻就明白了。第二步加调试打印。在循环里打印当前 i、栈内容、弹出下标和计算结果。很多人觉得打印代码很土但它定位单调栈问题是最高效的。你只需要看弹出时机对不对边界值有没有超预期。第三步用极端用例验证。空数组、单元素数组、整体递增、整体递减、全部相等的数组全都跑一遍。这些边界用例能一秒钟暴露你代码里假设是否成立。注意写单调栈题时最容易“看着代码没问题却死活不对”的场景几乎都在于更新答案的时机。比如柱状图最大矩形答案只在“弹栈”那一刻更新压栈时是不更新的。想清楚这一点代码的骨架就稳了。5.4 几个我用着很顺手的代码习惯最后分享几个我的个人习惯不一定每个人都喜欢但实测能减少低级错误栈里永远存下标不存值。需要值的时候统一通过 nums[stack[-1]] 获取。while 循环里比较用原数组的下标取值不要额外维护多个栈。在函数开头就把“返回结果数组”的长度和默认值定好再用固定写法初始化栈。在柱状图这种需要左右边界的题里直接先补哨兵再进入循环可以省掉后面大量的 if比如栈空、遍历结束后的收尾处理。这些习惯会在你写不同单调栈题时反复受益。尤其存下标这一点是从“能跑通”到“写得优雅”的分水岭。我自己在做完这几道题之后最大的感受是单调栈不是靠天赋理解的它就是一组“先淘汰、再结算”的思维框架。你只要愿意在纸上推演两三遍代码很快就会内化成肌肉记忆。建议看完这篇内容后去把每日温度和柱状图最大矩形各手写三遍直到不用看参考就能一气呵成默出来。到那时候你会发现很多看起来很难的区间、视野、跨度类问题本质都长一个样。