单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）。只有比栈顶元素小（或大）的元素才能直接进栈。

    单调栈的应用：寻找左/右侧，第一个比当前元素小/大的元素。
    可以简单记为以下条规则：

    • 无论哪种题型，都建议从左到右遍历元素。
    • 查找 「比当前元素大的元素」 就用 单调递增栈，查找 「比当前元素小的元素」 就用 单调递减栈。
    • 从 「左侧」 查找就看 「插入栈」 时的栈顶元素，从 「右侧」 查找就看 「弹出栈」 时即将插入的元素。

    原理好理解，做题的时候有点转换不过来。

    • 0496. 下一个更大元素 I

      1. class Solution:
      2.   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
      3.       stack = []
      4.       res_map = {}
      6.       for num in nums2:
      7.           while stack and num > stack[-1]:
      8.               res_map[stack[-1]] = num
      9.               stack.pop()
      10.           stack.append(num)
      12.       res = []
      13.       for num in nums1:
      14.           res.append(res_map.get(num, -1))
      15.       return res

    • 739. 每日温度 - 力扣（LeetCode）

      请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

    class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        n = len(temperatures)
        ans = [0 for _ in range(n)]
        stack = []

        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                idx = stack.pop()
                ans[idx] = i - idx
            stack.append(i)

        return ans

    0503 下一个更大元素 II

    给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

    看到循环链表，直接把列表复制一遍接在后面即可达到循环效果。
    看了《算法通关手册》的题解，发现没有必要真的复制一遍。既然是按照下标i遍历。直接在访问时候取模就不会越界了。学到一招~nums[i % size]

    class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1 for _ in range(2*n)]
        stack = []

        nums.extend(nums)
        for i in range(2*n):
            while stack and nums[i] > nums[stack[-1]]:
                idx = stack.pop()
                ans[idx] = nums[i]
            stack.append(i)
        return ans[:n]