单调栈（Monotonic Stack）本质上就是**“带约束的栈”：
在任何时刻，栈内元素都保持单调递增或单调递减**的顺序。一旦新元素破坏这个单调性，就不断出栈，直到恢复单调为止。
一、为什么要有单调栈？
很多问题的核心是这类需求：
对每个元素，快速找到它左边/右边第一个比它大或小的元素
比如：
- 下一个更大元素（Next Greater Element）
- 柱状图最大矩形
- 接雨水
- 股票价格跨度
如果暴力做：
每个元素向左/右扫描，时间复杂度是O(n²)
单调栈的价值在于：
把这类问题统一降到 O(n)
二、单调栈的核心不变量（Invariant）
单调栈始终维护一个顺序不被破坏的栈结构：
- 单调递增栈：栈底 → 栈顶，值越来越大
- 单调递减栈：栈底 → 栈顶，值越来越小
关键不是“递增/递减”本身，而是：
栈里留下的，都是“还没找到答案”的元素
一旦某个新元素能“解决”栈顶元素的问题，
栈顶就该出栈了。
三、为什么是 O(n)？
这是单调栈最容易被误解、但最重要的一点。
每个元素：
- 最多入栈一次
- 最多出栈一次
所以：
- 总入栈 ≤ n
- 总出栈 ≤ n
- 总操作 ≤ 2n →O(n)
哪怕有while循环，也不会爆。
四、栈里到底存什么？
这点非常关键，很多人会混淆。
两种常见存法
1. 存「值」
- 适合只关心大小关系
- 比如 Next Greater Element（只要值）
2. 存「下标」（更常见）
需要算距离、区间、面积时必须用下标
比如：
- 柱状图最大矩形
- 接雨水
- 最近更大/更小元素的距离
实战中90% 都是存下标
五、四种经典变体（一定要会的表）
| 目标 | 栈类型 | 扫描方向 |
|---|---|---|
| 右侧第一个更大 | 单调递减 | 左 → 右 |
| 右侧第一个更小 | 单调递增 | 左 → 右 |
| 左侧第一个更大 | 单调递减 | 右 → 左 |
| 左侧第一个更小 | 单调递增 | 右 → 左 |
一句口诀：
找「更大」用递减栈，找「更小」用递增栈
六、单调栈的本质理解（很重要）
你可以把单调栈理解为：
一种“延迟决策”的结构
- 元素入栈：
“我还不知道我的答案是谁” - 元素出栈：
“答案找到了，不需要我了”
栈中始终保存的是：
- 未来可能被某个元素解决的问题集合
八、什么时候你该想到单调栈？
看到这些关键词，条件反射就对了：
- 「第一个 / 最近的」
- 「左边 / 右边」
- 「比它大 / 比它小」
- 「区间 / 连续 / 最大 / 最小」
好，这里给你一组单调栈必刷经典题清单，我会按「题目 → 思路 → 单调栈过程 → 答案实现」完整走一遍。
从入门 → 核心 → 进阶，基本覆盖 90% 面试/竞赛场景。
九、经典题目
1、下一个更大元素（单调栈入门）
题目
给定数组nums，返回一个数组res，res[i]是nums[i]右边第一个比它大的元素，没有则为-1。
输入: [2,1,2,4,3] 输出: [4,2,4,-1,-1]思路
- 从左到右扫描
- 用单调递减栈
- 栈中保存「还没找到更大元素的下标」
单调栈过程
nums = [2,1,2,4,3] i=0: stack=[0] i=1: stack=[0,1] i=2: nums[2]=2 > nums[1]=1 → pop 1 → res[1]=2 stack=[0,2] i=3: 4 > 2 → pop 2 → res[2]=4 4 > 2 → pop 0 → res[0]=4 stack=[3] i=4: stack=[3,4]答案（Python）
defnext_greater(nums):n=len(nums)res=[
