算法概念速查
什么是单调栈？原理、识别信号与经典例题
更新：2026-07-03吴师兄图解算法
一句话定义
单调栈是栈的一种用法：每个新元素入栈前，先把栈里比它「差」的栈顶依次弹出，让栈从底到顶始终保持单调递增或递减。弹出发生的那一刻，答案就产生了——被弹出的元素刚好遇到了它右边第一个更大（或更小）的数。整个数组每个元素最多进栈一次、出栈一次，O(n) 解决暴力要 O(n²) 的「找最近的更大/更小元素」问题。
先打个比方
把它想成一排「还在等答案的人」：以每日温度为例，栈里压着的都是还没等到更热天气的日子，从底到顶温度一天比一天低。新的一天来了，只要它比栈顶那天热，栈顶就「等到了」——弹出去结算等了几天；结算完新的一天自己进栈，接着等未来更热的那天来叫醒它。
它是怎么运作的
关键在于想清楚「弹栈的瞬间意味着什么」。以找「下一个更大元素」为例：维护一个从底到顶递减的栈，新元素 x 进来时，所有比 x 小的栈顶依次弹出，它们的「下一个更大元素」都是 x；弹完之后 x 入栈，继续等它自己的答案。留到最后还在栈里的元素，右边没有更大的数，按题意填默认值（如 -1 或 0）。
栈里通常存下标而不是值：很多题最终要的是「距离」（等了几天、矩形宽度），只有下标能做减法；要用值的时候拿下标去数组里取即可。
什么时候用：识别信号
题目里出现下面任何一条，就该想到「单调栈」。
- 题目在问每个元素「右边（或左边）第一个比它大/小的元素」，如下一个更大元素、每日温度
- 按高度结算面积或容量：柱状图中最大的矩形、接雨水
- 你写出的暴力解是两层循环，内层在向右扫描找「最近的某个边界」
- 需要 O(n) 内对每个位置都求出一个「最近边界」，而不是只求全局最值
别和它们搞混
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
单调栈为什么是 O(n)？
每个下标最多入栈一次、出栈一次，所有弹栈操作加起来不超过 n 次。别被「循环里套 while」骗了——while 弹掉的是以后不会再处理的元素，总量是摊还线性的。
找「下一个更大」用递增栈还是递减栈？
找更大，栈内从底到顶递减（新来的大数一口气弹掉一串小数）；找更小则相反，栈内递增。记不住就想弹栈瞬间：谁被弹出，谁就拿到答案。
栈里该存下标还是存值？
默认存下标。要算距离、宽度时只有下标能做减法（如每日温度的 i−j）；需要值时用下标回数组里取，信息无损。