题目描述
给定两个没有重复元素的数组 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。
注意：
-
nums1和nums2中所有元素是唯一的。 -
nums1和nums2的数组大小都不超过1000。
官方难度
Easy
解决思路
最简单粗暴的解决思路，两层循环：
输入: nums1 = [2,4], nums2 = [1,2,3,4].
- 遍历
nums1，得到当前元素i即2. - 遍历
nums2，得到元素i (2)在当前nums2中的下标start. - 从
start开始找到nums2大于i (2)的元素3。
优化
这个题目考的是单调栈， 栈中存的是递减的数字，即当前输入元素是否大于栈顶元素，如果大于则出栈，否则将当前元素入栈。因为只有在当前元素大于栈顶元素的时候才出栈，因此，当出栈的时候，当前元素即为栈顶元素的下一个最更大值，可以构造出栈元素与下一个最大元素的映射，。以输入[1,9,3,2,5]为例子.
- 初始化记忆字典
memo, 并且1入栈 - 下一个元素
9判断是否大于栈顶元素1，大于则出栈，memo[1] = 9并且将9入栈； - 下一个
3判断是否大于栈顶元素9， 小于则入栈。 - 下一个
2判断是否大于栈顶元素3， 小于则入栈。 - 下一个
5判断是否大于栈顶元素2， 大于则出栈,memo[2] = 5。 - 继续判断下一个
5判断是否大于栈顶元素3， 大于则出栈,memo[3] = 5。 - 继续判断下一个
5判断是否大于栈顶元素9， 小于则入栈。
最终栈的结果为 [9, 5]，遍历nums1，如果当前元素不在memo中则添加-1，否则添加memo中存储的结果。
根据上面的分析，我们可以很容易的得到直接方案的流程如下：
- 遍历
nums2, 通过单调递减栈构造记忆函数memo - 遍历
nums1，如果当前元素不在memo中则添加-1，否则添加memo中存储的结果
基于这个流程，我们可以实现类似下面的代码：
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
res = []
stack = []
memo = {}
for i in nums2:
while stack and i > stack[-1]:
memo[stack[-1]] = i
stack.pop()
stack.append(i)
for j in nums1:
if j in memo:
res.append(memo[j])
else:
res.append(-1)
return res
总结
这题为Easy难度，大部分人都能想到暴力破解，但是如果能在面试过程中，不断优化，加入单调栈的思想，面试过程中是可以加分的。
