单调栈
单调栈总纲：最近更大/更小、左右边界、模板方向判断与经典题型总结。
[!info] related notes 算法面试题型 MOC 栈 每日温度 柱状图中最大的矩形 接雨水
单调栈
单调栈的本质是：
在遍历数组时，维护一批“仍然可能成为答案的候选元素”，并且让这些候选在栈里保持单调。
一句话记忆：
- 单调递增栈：从栈底到栈顶递增
- 单调递减栈：从栈底到栈顶递减
- 最常见用途：最近更大、最近更小、左右边界
一眼判断：这题是不是单调栈
看到下面这些信号，要往单调栈想：
- 求某个位置左边 / 右边第一个更大元素
- 求某个位置左边 / 右边第一个更小元素
- 要为每个元素确定左右边界
- 当前元素到来时，会淘汰一批不可能再成为答案的旧元素
- 题目在强调“最近满足大小关系的元素”
如果你发现：
- 当前元素会一次性解决掉前面多个位置的答案
- 被弹出的元素以后再也不可能更优
- 题目答案和大小比较、区间边界强相关
那大概率就是单调栈。
单调栈和普通栈的区别
普通栈更关心：
- 匹配
- 消除
- 碰撞
- 表达式上下文
单调栈更关心：
- 比较关系
- 候选淘汰
- 边界确定
也就是说：
- 普通栈处理“关系”
- 单调栈处理“比较”
单调栈在维护什么
它维护的不是“所有元素”，而是：
到当前为止，还没有失去资格的候选元素。
当新元素 x 到来时：
- 有些旧元素会被证明不可能再成为答案，于是出栈
- 剩下的元素仍然有资格，于是继续留在栈中
- 当前元素自己也可能成为后续候选，于是入栈
所以单调栈本质上是在做：
剪枝 + 延迟结算
做单调栈的固定五问
每道题先强制回答下面五个问题：
1. 我要找左边还是右边
- 找右边：常见写法是从左到右遍历，边走边给旧元素结算
- 找左边：常见写法是从左到右遍历，先弹不合法元素，再看栈顶
2. 我要找更大还是更小
别先背名字，先想：
- 当前元素到来时，谁应该被弹掉？
这是方向判断的核心。
3. 栈里存值还是存下标
大多数单调栈题都存下标，因为通常需要：
- 计算距离
- 回填答案
- 访问原数组值
- 确定左右边界
4. 弹栈时是在结算答案，还是只是删除无效候选
有些题一弹就能算答案，比如每日温度。
有些题弹栈只是清理不合法元素，比如求左边最近更大 / 更小时。
5. 需要哨兵吗
像柱状图最大矩形这类题，常常通过：
- 首尾补哨兵
- 最后统一清栈
来减少边界判断。
一页式速查表
| 目标 | 常见遍历方向 | 常见维护方式 | 弹栈含义 | 代表题 |
|---|---|---|---|---|
| 右边第一个更大 | 从左到右 | 单调递减栈 | 当前元素帮旧元素结算答案 | [[daily-temperatures |
| 右边第一个更小 | 从左到右 | 单调递增栈 | 当前元素帮旧元素结算答案 | [[largest-rectangle-in-histogram |
| 左边第一个更大 | 从左到右 | 弹掉不够大的元素 | 栈顶就是答案 | 最近更大元素类题 |
| 左边第一个更小 | 从左到右 | 弹掉不够小的元素 | 栈顶就是答案 | 最近更小元素类题 |
| 凹槽 / 边界结算 | 从左到右 | 按高度维护单调性 | 弹出的元素作为中间层或底部 | 接雨水 |
四种最常见模型
1. 求右边第一个更大元素
维护单调递减栈，栈里存下标。
当前元素更大时，说明它就是栈顶元素右边第一个更大值。
const ans = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
const j = stack.pop();
ans[j] = i;
}
stack.push(i);
}代表题：每日温度、下一个更大元素 I / II。
2. 求右边第一个更小元素
维护单调递增栈，栈里存下标。
当前元素更小时，说明它就是栈顶元素右边第一个更小值。
const ans = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && nums[i] < nums[stack[stack.length - 1]]) {
const j = stack.pop();
ans[j] = i;
}
stack.push(i);
}代表题：柱状图中最大的矩形。
3. 求左边第一个更大 / 更小元素
这一类常见思路不是“边走边给别人结算”，而是：
- 当前元素入栈前，先弹掉不合法候选
- 弹完以后，栈顶就是左边最近合法元素
const left = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && invalid(nums[stack[stack.length - 1]], nums[i])) {
stack.pop();
}
if (stack.length) {
left[i] = stack[stack.length - 1];
}
stack.push(i);
}4. 凹槽 / 区间边界结算
这类题弹栈时，弹出的元素往往不是答案本身，而是“中间层”。
最典型就是 接雨水：
- 被弹出的柱子是凹槽底部
- 新栈顶和当前柱子组成左右边界
每日温度
题目本质：
求每个位置右边第一个更大元素的位置差。
为什么栈里放下标而不是温度值：
- 因为最后要计算距离
- 温度值可以通过下标回原数组取
代码模板：
var dailyTemperatures = function(temperatures) {
const n = temperatures.length;
const ans = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const j = stack.pop();
ans[j] = i - j;
}
stack.push(i);
}
return ans;
};更完整题解见 每日温度。
柱状图中最大的矩形
题目本质：
对每个柱子，求它左边和右边第一个更小元素，从而得到最大可扩宽度。
关键理解：
- 弹栈时，当前元素是右边界
- 弹栈后的新栈顶是左边界
- 被弹出的柱子是当前确定面积的高度
更完整题解见 柱状图中最大的矩形。
接雨水
题目本质：
找到一个凹槽的左边界、底部和右边界，然后结算这段水量。
关键理解：
- 栈保持单调递减
- 当前柱子更高时，尝试填平中间低洼
- 弹栈得到底部，左右边界由当前柱子和新栈顶决定
更完整题解见 接雨水。
为什么 while 这么重要
很多人写单调栈时最容易犯的错，就是把 while 写成 if。
但单调栈里，新元素经常会连续淘汰多个旧元素。
比如：
- 每日温度中，一个更高温度可能一次性帮好几天结算答案
- 柱状图中，一个更矮柱子可能连续让多个更高柱子出栈
- 接雨水中，一个更高柱子可能连续填多个低洼结构
所以单调栈很多时候的本质就是：
当前元素触发了一次批量结算。
单调栈常见错误
1. 方向记反
不要死背“递增栈 / 递减栈”的名字，直接想：
- 我想让谁出栈？
- 出栈条件是
>还是<？
2. 该存下标却存了值
一旦涉及距离、边界、答案数组，基本都应该存下标。
3. 该用 while 却只写了 if
这会漏掉连续弹栈的情况。
4. 相等时处理不清楚
有些题要求严格大于，有些题允许大于等于。
所以比较符号必须和题意对应：
>还是>=<还是<=
这一点会直接影响去重和边界归属。
5. 边界没有统一
能补哨兵就补哨兵，能统一清栈就统一清栈。
怎么系统学习单调栈
第 1 阶段：先吃透“右边第一个更大”
建议先做：
- 每日温度
- 下一个更大元素 I
- 下一个更大元素 II
目标：
- 理解为什么当前元素能帮旧元素结算答案
- 理解为什么通常存下标
第 2 阶段：再做边界题
建议再做：
目标：
- 理解弹栈时不仅能结算单点答案，也能结算区间信息
- 理解哨兵和统一边界处理
第 3 阶段：做更多变形题
建议补：
- 最大矩形
- 子数组最小值之和
- 最小字典序 / 去重类单调栈
面试里怎么解释“为什么这题用单调栈”
可以直接按这个模板答：
- 这题本质是在找每个元素最近的更大 / 更小元素或边界
- 当前元素到来时，会淘汰一批不可能再成为答案的候选
- 被淘汰的元素以后不需要再看，所以适合用单调栈维护候选集
一段总结
单调栈不是单纯“背模板”的题型，而是一种利用大小关系做候选淘汰和批量结算的思维方式。
- 找最近更大 / 更小 -> 先想单调栈
- 要确定左右边界 -> 先想单调栈
- 写题时先想清楚：我要弹掉谁，弹掉后答案怎么结算
把这三点练熟，很多看起来不同的题都会收敛成同一个框架。