刷算法题的时候，单调栈是我最早觉得“有点玄”的数据结构之一。明明只是一条普通的栈，加上“单调”两个字，就突然能解决一批看起来必须暴力枚举的题目。最典型的就是LeetCode 739“每日温度”：给你一个温度数组，要求每个元素往后第一个温度更高的日子还要等几天。直接两层循环当然能做，但数据规模到10^5就麻了。单调栈呢？一趟扫完，时间O(n)，代码二十行以内。
这篇文章不打算只是贴模板，我想把单调栈背后的直觉、两套形态、经典题目和踩坑过程全部拆开讲。如果你正在刷LeetCode、准备算法面试，或者看过几篇单调栈文章但总觉得没吃透，希望这篇能帮你把这一块真正焊死。
1. 单调栈在解决什么类型的问题
1.1 缺少单调栈时：暴力枚举的代价
先回到“每日温度”这道题。题意很简单：给定列表 temperatures，返回一个数组 answer，其中 answer[i] 表示在第 i 天之后，需要等待多少天才会出现更高温度；如果之后都没有更高温度，则填0。
最常见的写法是两层循环：外层固定第 i 天，内层从 i+1 一直往后找，找到第一个比当前温度高的位置，记录下标差。代码很简单，我敢说绝大多数人第一次刷到它就是这种解法。
但暴力枚举的问题也很明显：内层循环在最坏情况下要反复扫描，整体复杂度是 O(n^2)。如果 n 是 10^5，就需要大约 10^10 次比较，在多数在线评测环境里几秒内跑不完，更别提实际业务里的性能要求。很多人做算法题一直停留在暴力层，不是因为不知道“可以优化”，而是没有一种工具能把“查找右侧第一个更大的数”这类操作从 O(n) 单次降到均摊 O(1) 总耗时。单调栈就是为这个大场景量身定做的。
1.2 单调栈的直觉：就像排队时只记住比自己高的个子
单调栈最核心的直觉，我一般用排队场景来理解。
想象你是队伍中某个位置的等待者，你要找的是“身后第一个比你高的人”。如果从左到右依次看过去，当一个高个子出现时，前面所有比他矮的、还在等待的人，都能在这一刻“结清答案”——他们的下一个更高的人，就是眼前这个高个子。而那些比高个子还高或和他一样高的人，无论如何都轮不到眼前这个人来结清，所以会继续留在候选池里等待。
单调栈就是把这个候选池用栈来组织，并且让栈内元素按某个单调方向排列。当新来的元素破坏了这个单调性时，就不断弹出栈顶元素，为它们“结清答案”，直到重新满足单调性，再把新元素压入栈。这样一来，每个元素最多被压入一次、弹出一次，整体代价就是线性的，非常干净。
2. 单调栈原理拆解：两种形态和两套模板
2.1 单调递增栈和单调递减栈怎么选
很多人第一关就卡在这里：到底什么时候用单调递增栈，什么时候用单调递减栈？
我的记忆方式很简单——看你要找的目标方向。如果你要找“右侧第一个更大的元素”，栈内元素要保持从栈底到栈顶递减。为什么？因为只有当新元素比栈顶元素更大时，栈顶才有机会结清答案；如果新元素比栈顶小或相等，说明它“不构成挑战”，应该压栈等待后续更大的元素。反过来，如果你要找“右侧第一个更小的元素”，栈内元素就要从栈底到栈顶递增，因为你需要遇到更小的元素来触发弹出结算。
下面这张表我建议直接记在笔记里：
| 目标 | 栈的方向（从底到顶） | 弹出触发条件 | 代表问题 |
|---|---|---|---|
| 右侧第一个更大的元素 | 递减 | 当前元素 > 栈顶 | 每日温度、下一个更大元素 |
| 右侧第一个更小的元素 | 递增 | 当前元素 < 栈顶 | 柱状图中最大的矩形 |
| 左侧第一个更小的元素 | 递增 | 当前元素 < 栈顶 | 柱状图边界、接雨水 |
注意，这里的“递增”“递减”一定要定义清楚，我指的是从栈底到栈顶的方向。不同资料说法可能相反，做题前先把定义统一，能避免很多混乱。
2.2 找右侧第一个更大元素的通用模板
以“找右侧第一个更大元素”为例，标准模板我习惯写成这样，栈里存下标，Python 代码如下：
def solve(nums): n = len(nums) ans = [-1] * n stack = [] # 栈底到栈顶递减，存下标 for i, x in enumerate(nums): while stack and x > nums[stack[-1]]: idx = stack.pop() ans[idx] = i # 或者依据题目需求记录具体值 stack.append(i) return ans这里有个关键点：为什么栈里要存下标而不是直接存值？因为很多题目最终要求返回“下标距离”或“天数差”，只有下标才能直接算距离。同时，只要有下标，通过 nums[stack[-1]] 随时都能拿到对应的值，信息一点也没丢。所以我的建议是无脑存下标，这是最通用的写法。
另一个容易忽略的操作顺序：先 while 弹出结算，再把当前元素入栈。千万不能反过来。如果先把当前元素入栈，栈顶就是它自己，后续比较会误判甚至死循环。
2.3 找相邻更小边界：另一类单调栈应用
找“右侧第一个更大元素”只是单调栈的一面，另一面同样重要：找某元素的左边和右边分别离它最近、比它小的元素。这种场景在“柱状图中最大的矩形”和“接雨水”里极其常见。
做法是维护一个从栈底到栈顶递增的栈。当新元素比栈顶元素小时，说明栈顶元素的“右侧第一个更小元素”就是当前元素；弹出栈顶后，新的栈顶元素（如果存在）就是那个被弹出元素的“左侧第一个更小元素”。通过这两条边界之间的距离，就能算出以该元素为高/基准的可扩展宽度。
很多初学者只知道“单调栈能找下一个更大”，却不知道它还能找左右两侧的小边界，导致柱状图矩形的题怎么也做不出来。其实是模板的镜像玩法，本质没有变。
2.4 为什么时间复杂度是O(n)
关于复杂度，我想多解释几句，因为面试时经常会被问。
在单调栈的整个运行过程中，每个元素只会被压入栈一次。至于弹出，看似 while 循环会弹很多次，但每次弹出一个元素，都代表那个元素永远不会再回到栈里。所以所有 while 循环累计弹出的总次数是 O(n)——每个元素最多被弹出一次。加上一层 for 循环本身也是 O(n)，整体就是 O(n) 时间，额外空间是栈的开销 O(n)。
这个“均摊”思想很重要。它不像二分那样严格每次操作都是 O(log n)，而是把总操作次数摊到 n 次遍历上，每次平均 O(1)。刷题解释复杂度时，说“每个元素入栈一次、出栈一次”是最稳妥的答案。
3. 经典题目实操：四道题带你彻底掌握单调栈
3.1 每日温度（LeetCode 739）
先说最经典的每日温度。给定 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，我们期望返回 [1, 1, 4, 2, 1, 1, 0, 0]。我平时面试新人时，喜欢要求对方把整个栈变化过程当场手推一遍，推完基本就知道是不是真懂了。
我用下标和值一起走一遍：
- i=0，温度73，栈空，直接入栈，栈内 [0]。
- i=1，温度74，74 > 栈顶73，弹出下标0，ans[0] = 1 - 0 = 1；然后1入栈，栈内 [1]。
- i=2，温度75，75 > 74，弹出下标1，ans[1] = 1；2入栈，栈内 [2]。
- i=3，温度71，71 < 75，不弹出，3入栈，栈内 [2,3]。
- i=4，温度69，69 < 71，4入栈，栈内 [2,3,4]。
- i=5，温度72，72 > 69，弹出下标4，ans[4] = 1；72 > 71，弹出下标3，ans[3] = 5 - 3 = 2；此时栈顶是下标2（75），72 < 75，停止弹出，5入栈，栈内 [2,5]。
- i=6，温度76，76 > 72，弹出下标5，ans[5] = 1；76 > 75，弹出下标2，ans[2] = 6 - 2 = 4；6入栈，栈内 [6]。
- i=7，温度73，73 < 76，7入栈，栈内 [6,7]。
最终结果就是 [1,1,4,2,1,1,0,0]。注意下标6和7都没有被任何更大的温度顶出，所以它们保持默认值0。这个手动推演的过程，我强烈建议每个人自己写一遍，比自己看十篇博客都管用。
代码和模板几乎一一对应：
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 ans3.2 下一个更大元素与环形数组（LeetCode 496 / 503）
下一道是“下一个更大元素 I”。题目给两个数组 nums1 和 nums2，nums1 是 nums2 的子集，要求返回 nums1 中每个数在 nums2 里右侧第一个比它大的数的值，没有就是 -1。
这道题最直接的做法是：先用单调栈把 nums2 中每个元素的“下一个更大元素”全部算出来，存进哈希表，然后遍历 nums1 按表取结果。为什么这样做合理？因为 nums2 本身是结构源，nums1 只负责查询，如果把查询也做一遍暴力循环，那复杂度又升回去了。用一个字典把单调栈结果记录下来，查询就是 O(1)，总复杂度 O(len(nums1)+len(nums2))。
写出来是这样：
def nextGreaterElement(nums1, nums2): nxt = {} stack = [] for x in nums2: while stack and x > stack[-1]: nxt[stack.pop()] = x stack.append(x) for x in stack: nxt[x] = -1 return [nxt[x] for x in nums1]这道题因为是按“值”查询，栈里直接存值没有问题。但如果你习惯存下标，也完全可以：用 nums2[stack[-1]] 做比较，最后把值填进字典。两种写法各有舒适区，我的建议是先用下标版本练熟，理解本质后再自由切换。
接下来的“下一个更大元素 II”是同一个命题，但数组变成了环形，也就是最后一个元素的下一个更大元素可以绕回数组开头找。处理环形数组有一个通用技巧：把数组“逻辑拉长”成两倍长度，遍历 i 从 0 到 2n-1，用 i % n 取实际下标。单调栈照常工作。
def nextGreaterElements(nums): n = len(nums) ans = [-1] * n stack = [] for i in range(2 * n): idx = i % n while stack and nums[idx] > nums[stack[-1]]: ans[stack.pop()] = nums[idx] if i < n: stack.append(i) return ans这里有个小细节值得提醒：入栈操作只在前 n 次循环进行，后面的循环只负责“继续比较剩余元素”，这样能避免同一个下标反复入栈，逻辑更清爽。栈中最终留下的元素自然是找不到更大元素的，答案保持 -1 即可。
3.3 接雨水（LeetCode 42）
接雨水是单调栈里难度明显上一个台阶的题，因为它是用单调递减栈来“结算凹槽”的。
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]，要求计算这排柱子能接多少雨水。用单调栈时，栈底到栈顶按柱子高度递减，栈里存下标。当新柱子高度大于栈顶高度时，说明当前栈顶柱子它自己处于一个凹槽底部的位置——它左侧有栈内比它高的柱子作为左墙，右侧有当前柱子作为右墙。这个凹槽能接的水量由左右两侧中较矮的一侧减去凹槽底的高度决定，宽度则是两侧下标之差再减1。
Python 代码如下：
def trap(height): n = len(height) ans = 0 stack = [] for i in range(n): while stack and height[i] > height[stack[-1]]: bottom = stack.pop() if not stack: break left = stack[-1] width = i - left - 1 h = min(height[left], height[i]) - height[bottom] ans += width * h stack.append(i) return ans注意到一个关键边界：当弹出栈顶后栈已经为空，说明左侧没有能挡住水的墙，凹槽不成立，直接 break 跳出 while。这个坑非常隐蔽，我第一次写的时候漏了，结果把左边没有墙的情况也拿来算水量，答案错得离谱。
我建议把接雨水和每日温度放在一起对比：每日温度是“遇到更大的就结算高度位置”，接雨水是“遇到更大的就结算水量面积”。模板骨架一样，差别在于弹出时需要多看一层——凹槽的底是当前弹出来的栈顶，左墙是弹出后的栈顶元素。
3.4 柱状图中最大的矩形（LeetCode 84）
柱状图中最大的矩形是另一道“劝退题”，它表面上是求面积，本质上是找每个柱子左右两侧第一个比它矮的位置，从而确定以它为高度的最大可扩展宽度。
经典例子 heights = [2, 1, 5, 6, 2, 3]。以高度5的柱子为例，它的左侧第一个比它矮的是下标1（高度1），右侧第一个比它矮的是下标4（高度2），所以高度5能扩展的宽度是4-1-1=2，能形成的矩形面积就是 5 * 2 = 10。这个答案也是全体柱子中的最大面积。
用单调递增栈处理时，遇到新柱子比栈顶柱子矮，栈顶柱子的“左右边界”就都确定了，可以立刻结算面积。为了处理最后栈里剩余的递增柱子，我会在原数组末尾补一个高度0的哨兵，让它把栈里所有柱子强制弹出，逻辑非常干净。
def largestRectangleArea(heights): heights.append(0) ans = 0 stack = [] 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 ans = max(ans, h * width) stack.append(i) return ans注意边界处理：弹出后栈为空，说明当前柱子左边没有任何比它矮的柱子，那 left 就是 -1，宽度就是当前下标到左边虚拟边界之间的范围，也就是 i。用 i - (-1) - 1 = i，正好正确。这个公式想清楚一次，之后写任何单调栈变体都不会乱。
为什么这题要用单调递增栈？因为要“遇到更矮的柱子时结算当前柱子”的矩形，只有栈底到栈顶递增，才能保证栈内每个元素左侧的元素都比它矮，当前新元素比栈顶矮时，栈顶的右侧边界也出现了。两个边界同步确定，结算自然成立。
3.5 移除k位数字（LeetCode 402）：单调栈的贪心变体
除了“找边界”，单调栈还能和贪心结合。移除k位数字这题要求从数字字符串中移除 k 位，使剩余数字组成的数尽可能小。
直观策略是：从左到右扫描，如果当前数字比前面保留的数字还小，那就应该把前面那个较大的数字删掉，因为把高位较大的数换成低位较小的数，整个数字会变小。这个过程天然就是单调栈——维护一个从栈底到栈顶递增的栈，遇到更小的数字时弹出栈顶，每弹一次相当于删除一位，直到 k 次用完。
def removeKdigits(num, k): stack = [] for ch in num: while k > 0 and stack and ch < stack[-1]: stack.pop() k -= 1 stack.append(ch) while k > 0: stack.pop() k -= 1 while stack and stack[0] == '0': stack.pop(0) return ''.join(stack) if stack else '0'这段代码有一个小毛病：stack.pop(0) 是 O(n) 操作，放在大样例上不够优雅。更稳妥的做法是用“指针+列表”或最后统一 lstrip('0') 处理前导零。我写在这里只是因为它更能直观看懂逻辑。面试时如果写到这里，建议顺手优化一下，比如用拼接结果时跳过前导0，或者在最后用循环统计前导零的个数再切片，这样能给面试官留一个“复杂度意识很强”的印象。
这道题已经不在“下一个更大元素”的范畴了，但它仍然是单调栈思维：你想维护一个单调序列，破坏单调的部分就要被删除或调整。这类题做多了，你会慢慢感觉到单调栈不是一个孤立的模板，而是一种利用“历史候选顺序”来消除无效比较的手段。
4. 单调栈常见误区与调试经验
4.1 相等元素的处理原则
我见过太多人栽在相等元素的处理上。以“下一个更大元素”为例，题目要求严格大于才算是“更大”，所以 while 里必须写大于（>），不能写大于等于（>=）。
如果写成大于等于，相等元素会被提前弹出结算，得到错误答案。比如每日温度数据 [76, 76, 73, 80]，第一个76本应在遇到80时得到答案3，但如果相等也弹出，它会在第二个76处提前结算成1，自然就错了。反之，如果你自己设计题目时想找“下一个大于等于”，那就要把比较符号改成 >=。做题前先确认题目要求是“严格大于”还是“大于等于”，这是最省时间的习惯。
4.2 栈里存值还是存下标
有些题答案要求返回“值”，比如下一个更大元素 I，栈里直接存值写起来简单。有些题要求返回“距离”，比如每日温度，则必须存下标。如果搞混，算距离时只能靠数组 indexOf 之类的操作，复杂度就退化了。
我的统一习惯是：一律先存下标。下标可以同时获得值和位置，是最通用的编码。等熟练以后，再针对值类问题优化成存值。面试手写代码时，建议先和面试官确认一句“我存下标，需要取值时用数组访问”，既展示思路又避免歧义。
4.3 栈空与边界条件的处理
单调栈代码最容易崩的位置就是 while pop 之后栈为空。
接雨水里，pop 后栈空表示左边没有墙，需要 break，不然会拿一个不存在的 left 去算宽度。柱状图最大矩形里，pop 后栈空说明 left 取 -1，用虚拟边界来算宽度。这两处的“栈空”含义完全不同，但核心逻辑都是统一的：先判断栈是否为空，再决定 left 的取值。我在代码里习惯用left = stack[-1] if stack else -1，一行解决，简单可靠。
另一个容易忽略的边界是：遍历结束后，栈里还会剩下一些元素。它们可能是找不到更大元素而保持默认答案的元素，也可能需要在最后结算。柱状图的最大矩形就是靠哨兵0保证最后结算，而每日温度不需要额外处理，因为答案默认就是0。不同题目，遍历结束后栈的状态不同，处理方式也不同——拿到题目先想清楚“最终栈里的元素还欠不欠答案”。
4.4 手写模拟两遍比看十遍博客有效
我说句掏心窝的话：单调栈看再多文章，都不如自己手动模拟一遍来得实在。
我第一次学的时候，也是看了很多博客，自认为懂了，结果写接雨水时连续交了三版错误的代码。后来老老实实把每日温度和接雨水的完整栈变化用纸笔画了一遍，标出每一步的 i、栈内下标、对应数值、弹出动作、结算结果。画完之后，脑子里对“什么是左边界、什么时候结算、为什么栈空要break”才有了真正的画面感。
我还有一个具体的调试技巧：在 while 循环里临时打印print(i, stack, ans)，观察每次弹出的前后状态，对比手推结果。尤其适合单调栈这种“状态被压着”的数据结构，局部错误很难一眼看出来，打印是最直接的定位工具。
5. 面试实战建议：从识别题目到写出模板
5.1 该怎么判断题目能用单调栈
面试时，判断一道题是否适合用单调栈，可以从关键词入手。只要题目中出现“右边第一个比它大的数”“左边第一个比它小的数”“下一个更大/更小元素”“环形数组中寻找下一个更大元素”，基本上就可以把单调栈放到候选方案的第一位。
还有一些题表面看不出“下一个”的关系，但本质也是在找左右边界，比如柱状图最大矩形、接雨水、最大宽度坡等。这类题通常涉及“以当前位置为基准，向两侧扩展直到遇到某个限制条件”，暴力做是 O(n^2)，如果想优化到 O(n)，就试试把限制条件建模成“第一个更小/更大的元素”。
我在面试中考察候选人时，如果对方能说出“这题我需要每个元素左右两侧第一个更小边界，所以用单调递增栈”，我基本就会认为他对这个知识点有体系化的理解；如果只能背出每日温度的模板，遇到变体就容易卡壳。
5.2 模板的四步记忆法
把单调栈代码浓缩成一个四步口诀，我自己面试前也会在心里过一遍：
第一步，确认方向，根据目标是“更大”还是“更小”决定用递增栈还是递减栈；第二步，栈存下标，统一用 nums 数组取值；第三步，while 循环，当前元素与栈顶比较，触发结算条件就 pop 并处理答案；第四步，把当前元素下标入栈，继续下一轮。
这四步不是死板的，但能有效防止漏写关键动作。我最常看到的新手错误就是只写了 while 和 pop，忘了入栈，或者入栈时存了值导致后面算不了距离。四步走一遍，基本能消灭这类低级错误。
还有一个小技巧：如果不确定代码写得对不对，可以先拿一个长度为3或4的例子手推一遍结果，再对照代码脑内执行。这个习惯比急着提交节省太多时间。
5.3 单调栈的扩展方向
单调栈学完之后，还可以往几个方向走。
第一个是单调队列。单调栈处理的是“维护历史最优候选”，而单调队列经常用于滑动窗口问题，比如“滑动窗口最大值”。两者的关系很像双胞胎：栈弹栈顶，队列弹队头；栈解决右侧/左侧最近关系，队列解决滑动窗口范围内的极值问题。会了单调栈，再去学单调队列会顺很多。
第二个是和其他算法配合。比如前缀和处理后的子数组问题、结合哈希表加速的变体、与贪心策略结合的删除类问题等。单调栈往往不是单独出现，而是作为整体思维的一个环节。
第三个是模板的语言迁移。虽然我用 Python 讲，但 C++ 里无非是vector<int> st; while (!st.empty() && nums[i] > nums[st.back()])这样的写法；Java 则是Deque<Integer> stack = new ArrayDeque<>();。思路完全一致，语言只是皮相。
最后聊一点我的个人体会
刷单调栈这段时间，我最大的感受是：这个结构解决的不是“某个单独问题”，而是一类“靠顺序比较就能消除冗余”的问题。它和我最早接触的暴力枚举差距非常大——暴力依赖“每个都查一遍”，单调栈依赖“只要前面的矮个子被高个子覆盖，就再也不用回头看它们”。面试官喜欢这类题，也是因为简单背后有推理，边界里藏着细节。
如果你刚开始学，别急着背题，先动手画两次栈变化，把比较方向、存值还是存下标、栈空怎么处理这三个问题想清楚。等你形成肌肉记忆之后，每日温度、接雨水、柱状图这类题就不再是背答案，而是每次都能快速写出来的基本功了。
