做算法题的人应该都有过这种体验第一次看到单调栈这个名词觉得它高大上甚至有点劝退。但实际上等你把这层窗户纸捅破你会发现它不过是一个维护了单调性的普通栈而已。Acwing算法基础课的数据结构章节里830这道题就是专门用来帮人捅破这层窗户纸的模板题。这篇文章我想从零开始把单调栈这个问题模型、运行过程、以及它背后为什么长得像的几类变形题全拆开讲一遍。不管你是为了考研408冲刺还是在准备校招面试的数据结构高频考点或者只是刷LeetCode时被“接雨水”“柱状图最大矩形”这类题折磨过这篇都值得你花十分钟读完。1. 单调栈到底解决什么问题先看懂这道题的存在意义1.1 典型问题场景与暴力解法瓶颈先把问题讲明白。Acwing 830题的原题是这样的给定一个长度为 n 的整数数列输出每个数左边第一个比它小的数如果不存在则输出 -1。举个例子输入5 3 4 2 7 5输出是-1 3 -1 2 2解释一下第一个数 3 左边没有数输出 -1第二个数 4 左边第一个比它小的是 3输出 3第三个数 2 左边虽然有 3 和 4但都比它大没有比它小的数输出 -1第四个数 7 左边第一个比它小的是 2输出 2第五个数 5 左边第一个比它小的是 2输出 2。很多人第一次做这道题条件反射就是暴力每一轮都往左边扫描找到第一个满足条件的数就停下。这个思路本身没有错问题是当 n 等于 10 的 5 次方甚至更大时极端情况下时间复杂度会退化到 O(n²)。比如输入是一个严格递减的序列5 4 3 2 1每一个数都要一路扫到最左边才能发现没有符合条件的数扫描的总次数就是 4321整体是平方级别。在竞赛和面试的时限下这个复杂度通常过不了。1.2 单调栈的核心思想淘汰永不可能成为答案的元素暴力慢在哪慢在每一轮都扫描了大量“明显不可能是答案”的元素。单调栈做的事情非常朴素在遍历过程中用一个栈维护候选答案集合并且保证这个集合里从栈底到栈顶是单调的。一旦发现某个元素不可能再成为后续任何数的答案就立刻把它淘汰出局。这里我用一个排队买票的类比来说。假设有一排人从队伍末尾往前看每个人都在找前面第一个比自己矮的人。如果队伍里站在前面的某个人 A比你高而且站得比你更靠前那么你后面的人往前看时会先看到 A但 A 不够矮不是答案再往前看如果又看到一个比 A 矮的人 B那 B 才可能成为答案。这里的关键在于A 比当前元素高、又比当前元素靠前那么在“找第一个更矮的人”这个需求下A 对后续所有元素来说都不可能成为答案了。因为它既不满足“更矮”的条件又会挡住后面的视线还不如直接把它“移除”掉让后面的人直接看到更靠前的 B。单调栈就是用这个逻辑在遍历每个元素时反复从栈顶弹出那些“又靠前、又不够小”的废元素弹到栈顶元素小于当前元素为止。此时栈顶元素就是当前元素左边第一个比它小的数。如果栈被弹空了就说明左边不存在比它小的数输出 -1。每个元素最多入栈一次、出栈一次总时间复杂度严格 O(n)。这就是单调栈的全部秘密。2. Acwing 830题完整推导从朴素思路到单调栈的进化过程2.1 题目描述与输入输出约定题目本身的输入输出约定很常规第一行输入一个整数 n表示数列长度第二行输入 n 个整数表示这个数列对于每个数输出它左边第一个比它小的数不存在就输出 -1每个输出之间用空格隔开。这里有一个细节值得说一下输出的时候最后一个数后面带不带空格在Acwing上都是能过的因为测评机是忽略行尾空格的。但如果你去参加某些严格比对输出字符串的考试就得注意控制格式这个我在第五章踩坑部分会再说。2.2 手把手模拟一遍单调栈运行过程我用题目自带的样例3 4 2 7 5来完整跑一遍单调栈初始状态栈为空栈顶指针 tt 0。处理 3栈为空直接判断左边没有比 3 小的数输出 -13 入栈此时栈内从底到顶是 [3]。处理 4栈顶是 33 4不弹出栈非空输出栈顶 34 入栈栈内变成 [3, 4]。处理 2栈顶是 44 2弹出 4新的栈顶是 33 2弹出 3栈空了说明左边没有比 2 小的数输出 -12 入栈栈内变成 [2]。处理 7栈顶是 22 7不弹出输出栈顶 27 入栈栈内变成 [2, 7]。处理 5栈顶是 77 5弹出 7新的栈顶是 22 5不弹出输出栈顶 25 入栈栈内变成 [2, 5]。最终输出-1 3 -1 2 2和题目样例完全一致。2.3 代码落地C参考实现与边界处理Acwing上大家最常用的写法是用数组模拟栈因为这样比 STL 的std::stack少一层封装常数更小而且代码可读性也不差。#include iostream using namespace std; const int N 100010; int stk[N], tt; int main() { int n; scanf(%d, n); for (int i 0; i n; i) { int x; scanf(%d, x); while (tt 0 stk[tt] x) { tt--; } if (tt 0) { printf(%d , stk[tt]); } else { printf(-1 ); } stk[tt] x; } return 0; }这段代码有几个地方值得细看1. while 而不是 if很多人第一次写的时候会把 while 误写成 if结果只弹出一个元素就开始判断。这不是小错误而是逻辑性错误。比如栈内是 [3, 4]处理 2 时如果只弹出 4栈顶就变成 3但 3 确实也不满足条件此时就会错误地输出 3。2. 等号的处理题目要求“左边第一个比它小的数”注意是严格小于。所以当栈顶元素等于当前元素时栈顶不满足“小于”的条件必须弹出。这就是stk[tt] x而不是stk[tt] x的原因。我在下一章会专门展开讲这个等号。3. 数组下标从 1 开始很多习惯从 0 开始写栈的人容易把空栈判断写成tt 0这样永远不可能为空就会出现越界访问。用 0 表示空栈、从 1 开始存元素写法和判断都干净很多。3. 单调栈的几种形态与易混点比较符号决定了你是否写错3.1 单调递增栈与单调递减栈的适用场景单调栈根据栈内元素从栈底到栈顶的排列方式分成两种形态栈的形态存元素的顺序典型用途核心while条件单调递增栈从栈底到栈顶从小到大找左边/右边第一个比当前元素小的值stk[tt] x时弹出单调递减栈从栈底到栈顶从大到小找左边/右边第一个比当前元素大的值stk[tt] x时弹出怎么记忆看 while 循环里弹出的条件。你想找“更小的值”那就把“不够小的”即大于等于当前元素的全部弹出去保证栈里的元素始终是从小到大排列你想找“更大的值”就把“不够大的”即小于等于当前元素的全部弹出去栈里元素从大到小排列。这个记忆方式我到现在还在用因为它比死记“哪种题用递增栈”要可靠得多。遇到变式题只要先想清楚题目要找的是比当前元素大还是比当前元素小就能定位用哪种单调栈。3.2 等号到底该不该处理两类题目的细微差别等号是单调栈里最容易踩的大坑。我把常见的题目需求分成三类找左边第一个比它小的数严格小于while 条件用相等的元素必须被弹出找左边第一个小于等于它的数非严格while 条件用相等的元素保留在栈里找左边第一个比它大的数严格大于while 条件用相等的元素必须被弹出。为什么“严格小于”和“小于等于”在代码上只差一个等号但结果可能差很多拿序列[2, 2]举例。求左边第一个比它小的数严格小于处理第一个 2栈空输出 -1处理第二个 2栈顶是 2由于2 2弹出栈空输出 -1。求左边第一个小于等于它的数处理第一个 2栈空输出 -1处理第二个 2栈顶是 2由于2 2不成立不弹出输出栈顶 2。同一个数组两种需求输出完全不同。很多人在做LeetCode或者其他OJ上“左边第一个更小元素”变式的时候因为套模板没注意这个等号就会在隐藏用例上翻车。3.3 左右方向的对称思考从模板题到变式题830题求的是“左边第一个”有些人做惯了就误以为单调栈只能正着遍历。实际上求“右边第一个”同样可以用单调栈只需要换个遍历方向从数组末尾往前遍历维护相同的单调规则。举个例子LeetCode 739题“每日温度”就是求每个元素右边第一个比它大的元素距离当前元素多远。你可以选择从右往左遍历维护单调递减栈也可以从左往右遍历在弹出元素时计算答案。两种都行复杂度都是 O(n)。我的建议是在初学阶段先把“左边”和“右边”两个方向的单调栈都自己手动推一遍彻底理解遍历顺序对答案的影响而不是只背一个方向的代码。因为面试时候考官很可能随手改个方向你要是只会套一套模板很容易暴露出没理解原理。4. 高频延伸题型实战单调栈不止能做“左边第一个更小”4.1 每日温度从模板到实际应用的第一次跳跃LeetCode 739题“每日温度”是单调栈经典题它的题意是给你一个数组temperatures对于每一天输出需要等多少天才能等到一个更高的温度如果之后都没有更高的温度输出 0。这道题从模板题跨出了一小步模板题输出的是“值”这道题输出的是“下标距离”。做法核心不变但栈里存的不是元素值而是元素下标。为什么存下标因为你输出答案时需要知道两个元素之间的距离如果只存值就丢失了位置信息。从前往后遍历数组维护一个单调递减栈因为要找的是右边第一个更大的温度所以要把“不够大”的元素弹出去。当遍历到一个新温度 x 时如果栈顶温度小于 x说明栈顶这一天的下一个更高温度就是当前这一天输出当前下标 - 栈顶下标然后弹出栈顶继续判断新的栈顶。这里有个很微妙的点每个元素被弹出时就是它答案确定的时候。如果某元素直到遍历结束都没被弹出说明它后面没有比它更大的元素答案就是 0。这个“弹出即结算”的思想其实是所有单调栈变式的底层逻辑。4.2 柱状图中最大的矩形一次遍历同时确定左右边界LeetCode 84题“柱状图中最大的矩形”是目前单调栈题里综合难度较高的一道。题目给一个非负整数数组每个值表示柱子的高度要求找到能勾勒出的最大矩形面积。常规思路是枚举每个柱子作为矩形的高度然后往左右扩展找到边界。暴力做法是对于每个柱子分别向左向右找到第一个比它矮的柱子两个方向都扫描时间复杂度 O(n²)。单调栈可以把左右边界的寻找合并成一次遍历。具体思路是维护一个单调递增栈从栈底到栈顶递增。当新元素比栈顶元素矮时栈顶元素作为矩形高度它的左边界是栈内下一个元素的位置右边界就是当前新元素的位置此时宽度就是右边界 - 左边界 - 1乘以当前高度得到一个候选面积。这个过程很容易让人困惑因为它把一个“二维扩展”的问题拆成了“一维结算”的过程。我第一次手推这道题时也花了不少时间。不过一旦想明白“弹出即结算”这个逻辑你会发现它和每日温度本质上是同一个套路元素在出栈时我们就能确定它作为“最小值”的左右影响范围。4.3 接雨水单调栈按层结算的巧妙视角LeetCode 42题“接雨水”是另一个高频题。这题双指针解法也很经典但用单调栈做思路非常特别它维护的是单调递减栈栈里元素从底到顶递减。当遇到一个比栈顶高的柱子时说明在栈顶位置形成了一个凹槽可以蓄水。每次弹出栈顶元素时把当前弹出的柱子作为“凹槽底部”然后看新的栈顶是否为凹槽左壁。如果左壁存在那么这一层能接的雨水面积就是(min(左壁高度, 当前柱子高度) - 凹槽底部高度) * (当前下标 - 左壁下标 - 1)。这种按层累计的做法和按列累计的思路非常不同。按列思考比较符合直觉按层思考则更贴近单调栈“状态压缩”的本质。我见过很多人在面试中被问到这道题会用双指针做法但一旦面试官追问“能不能用单调栈”就卡住了。这里的原因往往是平时只背了代码没有认真推过“弹出即结算”在接雨水里的含义。5. 实际做题踩过的坑与刷题顺序建议5.1 五大常见的“非算法性”翻车点单调栈本身逻辑不难但真正考试或笔试时翻车往往发生在代码层面而不是思路层面。我总结了自己和周围人常踩的五个坑1. 把 while 写成 if这个前面提过是最常见的“以为是理解错误其实是笔误”的情况。建议写完后自己跑一组需要连续弹出的数据比如3 2 1验证一下弹出行为。2. 等号方向搞反很多人在不同题目间切换时容易把和抄错。建议写代码前先在心里默念三遍“找小的弹大的等号找大的弹小的等号”再动笔。3. 空栈判断写错用数组模拟栈时tt初始化为 0判断空栈是tt 0或用!tt用 STL 时是stk.empty()。混用时最容易把两者搞混。4. 栈中存值和存下标的混淆830这类题目只输出值存值就行。但每日温度、柱状图面积、接雨水这些题目答案依赖位置必须存下标。存下标时比较的是a[stk[tt]]和a[i]而不是stk[tt]和a[i]这一行写错整个程序就废了。5. 输入输出性能问题如果 n 是 10 的 5 次方以上cin/cout不关同步、不换scanf/printf很容易超时。Acwing 平台对时限卡得比较严建议直接用scanf/printf或者习惯在代码开头加上ios::sync_with_stdio(false); cin.tie(0);。5.2 从模板题到熟练应用的学习路径刷单调栈我不建议一开始就上难题。比较稳妥的顺序是第一梯队Acwing 830题 LeetCode 739每日温度。这两题把“找值”和“找下标距离”两个最基础的方向打底第二梯队LeetCode 496下一个更大元素、LeetCode 503下一个更大元素II环形数组版。这两题训练单调栈在不同数据结构形态下的适应能力第三梯队LeetCode 84柱状图中最大矩形、LeetCode 42接雨水。这两题把单调栈和“区间扩展”“面积结算”结合是面试真正拉开差距的地方。每一梯度之间都应该留出时间自己手写代码跑通而不是只看题解觉得“懂了”就划走。尤其是84和42两道题我强烈建议你在草稿纸上把栈的变化过程完整模拟一遍最好是模拟两遍以上。5.3 面试中的提问技巧与表达方法单调栈在面试中经常作为“如何优化暴力解法”的切入点出现。面试官抛出问题后先说出暴力解法和它的时间复杂度再提出“使用单调栈可以把复杂度优化到 O(n)”这句话本身就能体现你的复杂度分析能力。但比这句话更重要的是下面这句解释每个元素最多入栈一次、出栈一次所以整体操作次数是 O(n)而不是 O(n²)。很多候选人会把单调栈的原理背得很熟但问到复杂度分析时会卡壳。把握住“出栈即结算、每个元素只被处理常数次”这个本质比背任何模板都关键。另外有一个表达上的小技巧给面试官讲单调栈不要上来就念代码先用例子模拟一轮。比如拿[3, 4, 2, 7, 5]走一遍展示出“弹出废元素、栈顶即答案”的过程。面试官往往能从这个过程中快速判断你是真的理解还是在背模板。写在最后我对单调栈的实际体会开始刷算法基础课的时候我对单调栈的第一印象是“又一个需要背的模板”。但做完了830题、739题、84题、42题之后我慢慢发现单调栈真正教给我的不是那些栈操作而是一种思维方式在处理序列问题时及时淘汰那些“未来也不再可能成为答案”的候选对象。这个思想不只是算法题里有用处理一些业务上的滑动窗口、最近匹配问题同样有效。现在我再回头翻Acwing 830题它给我最大的收获不是会写那十几行代码而是让我理解了“为什么每个元素只需要进出栈一次”这件事以及如何把这种分析手段迁移到其他类似问题里。如果你正在刷数据结构希望这篇文章也能帮你跨过这个坎。