Python下一个更大元素（刷题如风，常伴吾身）

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

输出: [-1,3,-1]

解释:

对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。

对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。

对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        window, d = [], dict()
        for num in nums2:
            while window and window[-1] < num:
                small = window.pop()
                d[small] = num
            window.append(num)
        return [d[num] if num in d else -1 for num in nums1]

科普一下，单调栈：

单调栈问题：

要知道单调栈的适用于解决什么样的问题，首先需要知道单调栈的作用。单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到下一个比他大（小）的元素（或者说可以）。

也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时我们通常使用单调栈。下面我们通过简单介绍单调减栈和单调增栈问题来进一步说明使用单调栈处理问题的过程。

什么时候使用单调栈？

通常是一维数组，要寻找任一元素右边（左边）第一个比自己大（小）的元素，且要求 O(n) 的时间复杂度

单调栈原理：

单调递增栈：从 栈底 到 栈顶 递增，栈顶大

单调递减栈：从 栈底 到 栈顶 递减，栈顶小

python模板套路：

1): 当前项向右找第一个比自己大的位置 —— 从右向左维护一个单调递减栈。

def nextGreaterElement_01(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack:
            res[i] = stack[-1]
        stack.append(nums[i])
    return res

或者 当前项向右找第一个比自己大的位置 —— 从左向右维护一个单调递减栈。

def nextGreaterElement_011(nums: list):
    length = len(nums)
    res, stack = [-1] * length, []
    for i in range(length):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            res[idx] = nums[i]
        stack.append(i)
    return res