1. 单调栈核心定义
什么是单调栈?
单调栈是一种特殊的栈结构,它保持栈内元素按照单调递增或单调递减的顺序排列。
两种主要类型:
- 单调递增栈:栈内元素从栈底到栈顶保持递增(栈底最小,栈顶最大)
- 单调递减栈:栈内元素从栈底到栈顶保持递减(栈底最大,栈顶最小)
简单记忆方法:
- 单调递增栈 = 栈内元素像上楼梯,越往上越大
- 单调递减栈 = 栈内元素像下楼梯,越往上越小
2. 单调栈的核心特点
与普通栈的区别
| 特性 | 普通栈 | 单调栈 |
|---|---|---|
| 元素顺序 | 任意顺序 | 严格单调递增/递减 |
| 核心操作 | 压入、弹出、查看栈顶 | 额外有维护单调性的操作 |
| 时间复杂度 | O(1) | 均摊O(n) |
| 主要用途 | 普通后进先出场景 | 解决"下一个更大/更小元素"等问题 |