一、单调栈

应用

给定一个序列，找出每个元素左边/右边离的最近的数在什么地方，或者找出每个元素左边第一个比它大的数在什么地方...

如：

思想

实现

• 随着i往右走的过程中， 可以用一个栈存放i左边的某些元素
• 最开始栈为空，每当i往右移，就让栈顶的元素和a[i]比较，如果栈顶大，就去掉，直到栈为空或者栈顶小，意味着找到了第一个比a[i]小的值，打印出来后，让a[i]进栈

时间复杂度分析

每个元素最多进栈一次，且最多出栈一次，只有2N个操作，所以时间复杂度为O(N)

题目：下一个最大的元素

https://leetcode-cn.com/problems/next-greater-element-i/

def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums2)
        m = len(nums1)
        stack = []
        next_large = {}
        for i in range(n-1, -1, -1):
            while len(stack) > 0 and stack[-1] <= nums2[i]:
                stack.pop()
            if len(stack) > 0:
                next_large[nums2[i]] = stack[-1]
            else:
                next_large[nums2[i]] = -1
            stack.append(nums2[i])
        return [next_large[num] for num in nums1]

二、单调队列

应用：求滑动窗口里的最大/小值