496. 下一个更大元素 I

Difficulty
easy
Tags
单调栈
URL
https://leetcode-cn.com/problems/next-greater-element-i/
Star
给你两个 没有重复元素 的数组 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 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

单调栈

思路
从后往前遍历数组nums2，遍历当前元素时，都和栈顶元素做一个比较，因为栈顶元素就是作为比当前元素更大的值放到结果中的（这也是为说明需要从前往后遍历），所以栈顶一定要比当前值大。
题解
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = {}
        stack = []
        for i in range(len(nums2)-1, -1, -1):
						# 栈顶的一定要比当前值大才可以
            while stack and stack[-1] < nums2[i]:
                stack.pop()
            res[nums2[i]] = stack[-1] if stack else -1
            stack.append(nums2[i])
        return [res[i] for i in nums1]