Stack

算法思路：

定义： 栈里元素维持由栈底到栈顶从大到小的顺序叫递减栈。跟最小堆一样，递减栈的栈首元素最小。

反之是递增栈，不过此法因为用递减栈比较多，所以统称递减栈。通常是将下标而不是值放入到栈中，这样还可以知道元素间的距离。

求较大值 -> 递减栈
求较小值 -> 递增栈

递减栈 vs heap
实现上几乎一样，详见算法知识点目录。区别在于元素间是否需要保持顺序或者是否是stream

应用：

1. 数组不能打乱顺序且求极值

注意事项：

1. 跟最小堆一样，当元素大于栈顶元素的时候才倒逼栈内元素出栈。
2. 记得是stack[-1]看栈顶元素不是stack[0]

Python代码：

stack = []
for i in range(len(li)):
	while stack and li[i] > li[stack[-1]]:
		index = stack.pop()

	stack.append(i)

LeetCode 503 Next Greater Element II
核心思想: 原数组复制一遍，用新数组完全做一遍递减栈，最后才截取结果

例子：

def nextGreaterElements(self, nums: List[int]) -> List[int]:
	num_list = nums * 2
	result, stack = [0] * len(num_list), []
	for i in range(len(num_list)):
		while stack and num_list[i] > num_list[stack[-1]]:
			index = stack.pop()
			result[index] = num_list[i]
		stack.append(i)

	while stack:
		index = stack.pop()
		result[index] = -1
	return result[:len(nums)]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。