什么是单调栈？
单调栈是一种特殊的栈结构，栈内元素保持单调性（递增或递减）。
但这只是表象！单调栈的本质是：
用栈动态维护"全局待定"元素集合，通过弹出操作完成"全局问题→局部确定"的转化过程。
核心思想
┌─────────────┐
│ 全局问题 │
└──────┬──────┘
│ 从左到右扫描
↓
┌─────────────┐ 触发条件满足
│ 单调栈中 │ ────────────→ ┌─────────────┐
│ (全局待定) │ │ 弹出栈 │
└─────────────┘ │ (局部确定) │
└─────────────┘
- 栈中元素 = 全局待定的元素（还没被"确定"）
- 弹出元素 = 局部确定的元素（作用范围确定了）
- 栈的单调性 = 优先级顺序的体现
识别单调栈问题的三个信号
信号1：全局 vs 局部
问题涉及"全局最优"到"局部确定"的转化
例如：
- 最少操作次数：全局操作 → 遇到小值后局部确定
- 接雨水：全局高度 → 遇到更高柱子后局部确定
- 下一个更大元素：全局查找 → 遇到更大值后局部确定
信号2：前后元素关系
当前元素会影响之前元素的有效性
例如：
- 最少操作次数：遇到小值，大值失效（被隔离成孤岛）
- 接雨水：遇到高柱，低柱可以接水了
- 最大矩形：遇到低柱，高柱的范围确定了
信号3：优先级顺序
有明确的优先级（最小/最大优先）
关键特征：
- 小的先处理 → 单调递增栈
- 大的先处理 → 单调递减栈
识别检查清单
遇到问题时，问自己：
- 元素之间有优先级吗？（大小、高低、远近）
- 当前元素会让之前的元素失效吗？
- **问题涉及"范围确定"或"局部最优"**吗？
- 需要知道"下一个更大/更小"元素吗？
- 有明确的分隔符或边界吗？
如果3个以上✓，很可能是单调栈问题！
单调栈通用模板
func monotoneStack(nums []int) int {
result := 0
stack := []int{} // 或 []ElementType{}
for i, num := range nums {
// 1. 处理分隔符（如果有）
if isSeparator(num) {
stack = stack[:0]
continue
}
// 2. 弹出不满足单调性的元素
// 这些元素的"局部解"确定了
for len(stack) > 0 && shouldPop(stack[len(stack)-1], num) {
// 可选：在弹出时处理该元素
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 计算top的贡献
result += calculate(top, stack, num)
}
// 3. 判断是否需要新操作
// - 栈空 → 需要
// - 栈顶满足条件 → 可能需要
if needNewOperation(stack, num) {
result++
stack = append(stack, num)
}
// 如果栈顶 == num，可能不需要操作
}
return result
}
// 核心函数：
// - isSeparator(num)：是否是分隔符
// - shouldPop(top, cur)：是否弹出栈顶
// - 单调递增栈：top > cur
// - 单调递减栈：top < cur
// - needNewOperation(stack, num)：是否需要新操作
// - calculate(top, stack, num)：计算贡献（可选）
三层核心洞察
洞察1：基线数量
有多少个需要处理的单位，至少需要多少次操作
- 最少操作次数：不同值的个数 = 基线操作数
- 接雨水：能接水的位置 = 基线容量
洞察2：分隔增量
单位之间被分隔，会增加处理次数/成本
- 最少操作次数：相同值被小值分隔 → 操作数+1
- 接雨水：连续低洼被高柱分隔 → 分段计算
洞察3：局部确定条件
遇到什么条件，元素的局部解就确定了？
- 最少操作次数：
当前值 < 栈顶或当前值 == 0 - 接雨水：
当前高度 > 栈顶高度 - 下一个更大元素：
当前值 > 栈顶
示例详解：将所有元素变为0的最少操作次数
LeetCode 3542: 将所有元素变为0的最少操作次数
问题描述
给你一个大小为 n 的非负整数数组 nums。你的任务是对该数组执行若干次（可能为 0 次）操作，使得所有元素都变为 0。
在一次操作中，你可以：
- 选择一个子数组
[i, j]（0 <= i <= j < n） - 将该子数组中所有最小的非负整数设为 0
返回使整个数组变为 0 所需的最少操作次数。
注意：一个子数组是数组中的一段连续元素。
示例1：
输入: nums = [0,2]
输出: 1
解释:
- 选择子数组 [1,1]（即 [2]），最小非负整数是 2
将所有 2 设为 0 → [0,0]
示例2：
输入: nums = [3,1,2,1]
输出: 3
解释:
- 选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1
将所有 1 设为 0 → [3,0,2,0]
- 选择子数组 [2,2]（即 [2]），将 2 设为 0 → [3,0,0,0]
- 选择子数组 [0,0]（即 [3]），将 3 设为 0 → [0,0,0,0]
示例3：
输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
- 选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1
将所有 1 设为 0 → [0,2,0,2,0,2]
- 选择子数组 [1,1]（即 [2]），将 2 设为 0 → [0,0,0,2,0,2]
- 选择子数组 [3,3]（即 [2]），将 2 设为 0 → [0,0,0,0,0,2]
- 选择子数组 [5,5]（即 [2]），将 2 设为 0 → [0,0,0,0,0,0]
问题分析
核心洞察
洞察1：0的分隔作用
0就像一道不可逾越的墙，0将数组分隔成独立的区域。
举例：[0,3,2,0]
- 被0分隔成两个区域：
[3]和[2] - 每个区域需要独立处理
- 所以总共需要2次操作
洞察2：最小值优先策略
在非0的连续子数组中，每次操作都应该处理当前的最小值。
为什么？
- 处理最小值时，可以把该值的所有出现位置一起清零
- 处理最小值后，比它大的值会被分隔成更小的子区域
- 这确保了操作次数最少
洞察3：小值"隔离"大值
更深层的洞察：当处理一个小值时，大值会被0分隔成孤岛。
举例：[3,1,2,1]
- 处理1后：
[3,0,2,0] - 3被隔离成孤岛
[3]，需要单独处理 - 2被隔离成孤岛
[2]，需要单独处理
这就是"全局→局部"的转化！
三层洞察应用
洞察1：基线数量
- 不同值的个数 = 基线操作数
[1,2,3,4,5]→ 5个不同值 → 至少5次操作
洞察2：分隔增量
- 相同值被小值分隔 → 增加操作数
[2,1,2]→ 值2被1分隔成2个孤岛 → 需要3次操作（处理1 + 2个孤岛的2）
洞察3：局部确定
- 遇到更小值或0 → 大值的局部解确定
[3,1,...]→ 遇到1时，3的作用范围确定为[0,1)
方法演进
方法1：递归模拟（直观但慢）
思路：按0分割 → 找最小值 → 递归处理子区域
func minOperations(nums []int) int {
// 按0分割成多个区域
// 对每个区域：找最小值，标记为0，递归处理子区域
// 时间复杂度：O(n²) 最坏情况
}
问题：递归+数组修改开销大，会超时
方法2：按值分组（离线算法）
思维跳跃：既然最小值优先，那就按值从小到大排序处理！
关键洞察：对于每个值，检查它的相邻两个位置之间是否有比它小的值
- 如果有，说明处理小值后会产生分隔
- 段数 = 该值被分成多少段
func minOperations(nums []int) int {
// 1. 按值分组，记录每个值的位置
// 2. 按值从小到大排序
// 3. 对每个值，检查相邻位置间是否有更小值
// 时间复杂度：O(n×k)，k是不同值的个数
}
示例 [1,2,1,2,1,2]：
- 值1（位置0,2,4）：相邻位置间没有更小值 → 1段
- 值2（位置1,3,5）：
- 位置1-3间有1（1<2）→ 分隔！
- 位置3-5间有1（1<2）→ 分隔！
- 总共3段
- 总计：1 + 3 = 4次操作 ✓
问题：虽然正确，但在极端情况下仍会超时
方法3：单调栈（最优解）
思维的飞跃：
从"最小值优先"和"小值隔离大值"出发：
- 从左到右扫描时，如果遇到小值，之前的大值就不重要了（会被隔离）
- 所以只需维护"还有用的值" → 这些值必然是递增的
- 用栈维护 → 单调递增栈
算法描述：
维护一个单调递增栈，栈中保存当前"活跃"的不同值：
func minOperations(nums []int) int {
operations := 0
stack := []int{} // 单调递增栈
for _, num := range nums {
if num == 0 {
// 0是分隔符，清空栈
stack = stack[:0]
continue
}
// 弹出所有 > num 的元素
// 为什么？因为这些大值会被隔离成孤岛
for len(stack) > 0 && stack[len(stack)-1] > num {
stack = stack[:len(stack)-1]
}
// 如果栈为空或栈顶 < num，需要新操作
if len(stack) == 0 || stack[len(stack)-1] < num {
operations++
stack = append(stack, num)
}
// 如果栈顶 == num，不需要操作（已在计划中）
}
return operations
}
时间复杂度：O(n) - 每个元素最多入栈出栈各一次
空间复杂度：O(k) - k是不同值的个数
详细示例演示
示例1：[1,2,0,5,1,2,1]
步骤1: num=1
栈: [] → 栈空，需要操作
操作数: 1
栈: [1]
步骤2: num=2
栈: [1] → 栈顶1 < 2，需要操作
操作数: 2
栈: [1, 2]
步骤3: num=0
栈: [1, 2] → 遇到0，清空栈（硬分隔）
操作数: 2
栈: []
步骤4: num=5
栈: [] → 栈空，需要操作
操作数: 3
栈: [5]
步骤5: num=1
栈: [5] → 弹出5（5 > 1，5被隔离）
栈: [] → 栈空，需要操作
操作数: 4
栈: [1]
步骤6: num=2
栈: [1] → 栈顶1 < 2，需要操作
操作数: 5
栈: [1, 2]
步骤7: num=1
栈: [1, 2] → 弹出2（2 > 1，2被隔离）
栈: [1] → 栈顶1 == 1，不需要操作
操作数: 5
栈: [1]
最终答案：5次操作 ✓
示例2：[3,1,2,1]
步骤1: num=3 → ops=1, 栈=[3]
步骤2: num=1 → 弹出3, ops=2, 栈=[1] (3被隔离)
步骤3: num=2 → 栈顶1<2, ops=3, 栈=[1,2]
步骤4: num=1 → 弹出2, 栈顶1==1, ops=3, 栈=[1] (2被隔离)
最终答案：3次操作 ✓
示例3：[1,2,1,2,1,2]
步骤1: num=1 → ops=1, 栈=[1]
步骤2: num=2 → ops=2, 栈=[1,2]
步骤3: num=1 → 弹出2, 栈顶==1, ops=2, 栈=[1]
步骤4: num=2 → ops=3, 栈=[1,2]
步骤5: num=1 → 弹出2, 栈顶==1, ops=3, 栈=[1]
步骤6: num=2 → ops=4, 栈=[1,2]
最终答案：4次操作 ✓
核心理解
栈的含义
栈中保存的是**“当前需要独立操作处理的不同值”**（单调递增）
为什么弹出大值？
当遇到小值 num 时：
- 所有比 num 大的值都会被"隔离成孤岛"
- 孤岛内的大值会在局部处理
- 所以这些大值不再需要全局操作，弹出！
弹出 = 从全局计划移除（因为会变成局部问题）
为什么重复值不操作？
如果 栈顶 == num，说明之前已经安排了处理这个值的操作，不需要重复。
为什么单调递增？
因为我们总是弹出比当前值大的元素，所以栈自然保持递增。
常见单调栈问题分类
| 问题类型 | 栈类型 | 弹出条件 | 典型题目 |
|---|---|---|---|
| 下一个更大元素 | 递减栈 | cur > top |
LC 496, 503 |
| 下一个更小元素 | 递增栈 | cur < top |
LC 1475 |
| 矩形面积 | 递增栈 | cur < top |
LC 84, 85 |
| 接雨水 | 递增栈 | cur > top |
LC 42 |
| 移除K个数字 | 递增栈 | cur < top |
LC 402 |
| 最少操作次数 | 递增栈 | cur < top |
LC 3542 |
记忆口诀
单调栈四问
- 为什么栈？ → 动态维护全局待定元素
- 为什么单调？ → 体现优先级顺序
- 为什么弹出？ → 局部解确定，转化完成
- 为什么入栈？ → 新的全局待定元素
一句话精髓
单调栈 = 用栈维护"全局待定"集合，通过弹出完成"全局→局部"的动态转化。
调试技巧
如果单调栈不工作，检查：
- 单调性方向反了？递增 vs 递减
- 弹出条件错了？
>vs>= - 忘记处理相等情况？
- 结果统计位置错了？入栈时 vs 弹出时
- 边界条件遗漏？栈空、数组开头/结尾
总结
单调栈的精髓：
- 不是机械的"维护单调性"
- 而是动态的"全局→局部转化"
- 栈只是载体，转化才是本质
从洞察到最优解的思维路径
- 观察到分隔规律 → 按分隔符分割独立处理
- 观察到优先级顺序 → 按优先级排序处理
- 观察到相互影响关系 → 小值会隔离大值
- 从隔离想到范围确定 → 大值的作用范围确定
- 从范围确定想到维护有效集 → 单调栈
- 单调栈 = 动态维护活跃值集合
关键跳跃：从"全局排序"到"局部维护"，从"离线"到"在线"。
当你理解了"转化"，单调栈就不再神秘了！