单调栈
什么是单调栈
顾名思义,单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。
为了描述方便,以下举例及伪代码以维护一个整数的单调递增栈为例。
- 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小
- 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大
单调栈的特性
对于单调递增栈。若当前进栈元素大于栈顶元素,则会把栈顶元素弹出栈。这个性质能保证栈顶元素是栈内小于它的元素遇到的第一个大数。
1 | def findFirstGreatNum(arr): |
顾名思义,单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。
为了描述方便,以下举例及伪代码以维护一个整数的单调递增栈为例。
对于单调递增栈。若当前进栈元素大于栈顶元素,则会把栈顶元素弹出栈。这个性质能保证栈顶元素是栈内小于它的元素遇到的第一个大数。
1 | def findFirstGreatNum(arr): |