python 下一个更大的元素(leetcode)

python 下一个更大的元素(leetcode)

给你两个没有重复元素的数组nums1 和 nums2 ,其中nums1 是 nums2 的子集。
请你找出nums1 中每个元素子在nums2 中的下一个比较大的值。
nums1 中数字x 的下一个更大元素是指nums2 中对应位置的右边的第一个比x 的元素。如果不存在，对应位置输出-1。

• 解法一
  • 遍历查找
    代码如下：

class Solution1:
    def nextGreaterElement(self, nums1, nums2):
        res = []
        for i in range(len(nums1)):
            index = nums2.index(nums1[i]) + 1
            while index < len(nums2):
                if nums1[i] < nums2[index]:
                    res.append(nums2[index])
                    break
                index += 1
            else:
                res.append(-1)
        return res

• 解法二
• 利用栈的单调性
• 代码如下

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        res, stack = [], []
        length, tmp = len(nums2), dict()
        for index in range(length):
            # 单调递减
            while stack and nums2[index] > stack[-1]:
                tmp[stack.pop()] = nums2[index]
            # 栈顶元素比 当前值大
            stack.append(nums2[index])

        return [tmp.get(num, -1) for num in nums1]