单调栈详解：从Acwing 830模板题到LeetCode高频变式

做算法题的人应该都有过这种体验：第一次看到单调栈这个名词，觉得它高大上，甚至有点劝退。但实际上，等你把这层窗户纸捅破，你会发现它不过是一个维护了单调性的普通栈而已。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，每一个数都要一路扫到最左边才能发现没有符合条件的数，扫描的总次数就是 4+3+2+1，整体是平方级别。在竞赛和面试的时限下，这个复杂度通常过不了。

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 小的数，输出 -1；
• 3 入栈，此时栈内从底到顶是 [3]。

处理 4：

• 栈顶是 3，3 < 4，不弹出；
• 栈非空，输出栈顶 3；
• 4 入栈，栈内变成 [3, 4]。

处理 2：

• 栈顶是 4，4 >= 2，弹出 4；
• 新的栈顶是 3，3 >= 2，弹出 3；
• 栈空了，说明左边没有比 2 小的数，输出 -1；
• 2 入栈，栈内变成 [2]。

处理 7：

• 栈顶是 2，2 < 7，不弹出；
• 输出栈顶 2；
• 7 入栈，栈内变成 [2, 7]。

处理 5：

• 栈顶是 7，7 >= 5，弹出 7；
• 新的栈顶是 2，2 < 5，不弹出；
• 输出栈顶 2；
• 5 入栈，栈内变成 [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 循环里弹出的条件。你想找“更小的值”，那就把“不够小的”（即大于等于当前元素的）全部弹出去，保证栈里的元素始终是从小到大排列；你想找“更大的值”，就把“不够大的”（即小于等于当前元素的）全部弹出去，栈里元素从大到小排列。

这个记忆方式我到现在还在用，因为它比死记“哪种题用递增栈”要可靠得多。遇到变式题，只要先想清楚题目要找的是比当前元素大还是比当前元素小，就能定位用哪种单调栈。

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题，它给我最大的收获不是会写那十几行代码，而是让我理解了“为什么每个元素只需要进出栈一次”这件事，以及如何把这种分析手段迁移到其他类似问题里。如果你正在刷数据结构，希望这篇文章也能帮你跨过这个坎。