题目要求

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

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

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

解题思路

1. 对于找下一个更大值的问题，用到的解决问题的模板是单调栈。本题可以维护一个单调减的栈。
2. 根据题目要求，容易想到用数组实现栈；用字典保存nums2中每个元素的下一个更大值，其中键为nums2中的元素，值为下一个更大值。
3. 最后搜索nums1中的所有元素在nums2中的值，保存到数组中输出即可。

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dic = {}
        stack = []
        # 首先找出nums2中每个元素的下一个最大值
        for i in range(len(nums2)):
            # 若栈为空，nums2[i]直接添加其中
            if len(stack) == 0:
                stack.append(nums2[i])
            # 栈不为空，维护栈为单调减
            else:
                # nums2[i]小于等于栈顶元素，即可保证栈单调减，因此nums2[i]直接入栈
                if nums2[i] <= stack[-1]:
                    stack.append(nums2[i])
                # nums2[i]大于栈顶元素，即栈顶元素的下一个最大值为nums2[i]
                else:
                    # 若栈不为空并且栈顶元素更新后仍然小于nums2[i]，当前栈顶元素下一个最大值仍为nums2[i]
                    while len(stack) != 0 and nums2[i] > stack[-1]:
                        # 在字典中添加键值对，作为记录
                        dic[stack[-1]] = nums2[i]
                        stack.pop()
                    # 当单调栈空了或者当前栈顶元素大于等于nums2[i]，此时将nums2[i]压栈，依然维护栈为单调减的
                    stack.append(nums2[i])
        # 将栈中剩余元素（不存在下一个最大值的元素）出栈，同样在字典中添加键值对，作为记录
        for i in range(len(stack)):
            dic[stack[i]] = -1
        # 清空实现栈的数组（也可重新开一个空数组）用于保存返回结果
        stack = []
        # 遍历nums1中的所有值，在dic中搜索找到符合题意的值，并保存
        for i in range(len(nums1)):
            stack.append(dic[nums1[i]])
        return stack

知识点

单调栈往往用于解决下一个最值的问题。