单调栈

Posted on Edited on

什么是单调栈

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。
为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

  • 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
  • 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

单调栈的特性

对于单调递增栈。若当前进栈元素大于栈顶元素，则会把栈顶元素弹出栈。这个性质能保证栈顶元素是栈内小于它的元素遇到的第一个大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findFirstGreatNum(arr):
    # stack存放arr的元素下标
    stack = []
    result = [-1] * len(arr)
    for (i, n) in enumerate(arr):
        while stack and n > arr[stack[-1]]:
            # 说明n是第一个大于arr[stack[-1]]的数
            idx = stack.pop()
            result[idx] = n
        stack.append(i)
    print result


arr = [3,4,2,6,4,5,2,3]
# 6是第一个大于4，2的元素
findFirstGreatNum(arr)

输出：[4, 6, 6, -1, 5, -1, 3, -1]