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 核心思想: 原数组复制一遍，用新数组完全做一遍递减栈，最后才截取结果
结果数组默认值为-1而不是0，这样不用处理stack剩下的元素

例子：

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

算法分析：

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