单调栈

什么是单调栈

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

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

单调栈的特性

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

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]