单调栈___2023-08-31
单调栈
目录
问题背景
单调栈要解决如下问题:
对于数组中每一个数, 希望能获知其左右两侧离ta最近的比ta大的数的下标
举例: 对于一个数组[1, 4, 2, 8, 5, 7], 希望获得下表:
| index | value | left greater | right greater |
|---|---|---|---|
| 0 | 1 | / | 1 -> 4 |
| 1 | 4 | / | 3 -> 8 |
| 2 | 2 | 1 -> 4 | 3 -> 8 |
| 3 | 8 | / | / |
| 4 | 5 | 3 -> 8 | 5 -> 7 |
| 5 | 7 | 3 -> 8 | / |
想要所有信息, 如果暴力那么每次都是整体遍历, 时间复杂度$O(n^2)$
单调栈结构能使得整体时间复杂度优化至$O(n)$, 那么单次就是常数级别了
流程
准备一个栈作为我们的单调栈
由于要求两侧大的数, 所以栈的单调性是从栈底到栈顶由大到小
若要求更小的数, 反一反即可
我们先假定数组中无重复元素
遍历数组, 对于每个数:
- 如果符合单调性(当前数小于栈顶数), 压栈
- 如果栈顶小于入栈数, 那么弹栈, 直到能压栈
一个数被弹出, 其信息即可生成:
- 其左侧最近的比ta大的数, 就是压在ta下面的那个数
- 其右侧最近的比ta大的数, 就是等着压栈的那个数
下面没数就说明左侧没有比ta大的数, 记为空
当然, 会出现所有数遍历完成后, 还有数留存于栈中
此时我们要清算剩余的数:
- 依次弹出
- 规则同上, 只是右侧的信息一律记为空
关于数组中有重复数据, 在搞清原理后自然能明白怎么做
原理分析
我们记一个数a被弹出时, 等着压栈的数叫b, a正下方的叫c
为什么b是a右侧最近的较大的数?
根据单调栈的定义, 栈中的元素从栈底到栈顶是从大到小的
因此a的上方全是比ta小的, 第一个出现的比a大的数为了进栈会一直弹栈
因此b必定是右侧第一个比a大的数