题目

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

解题思路

1、暴力破解

优先处理nums2中的数值，找出每个数值对应题目要求的数，然后使用map进行存储：nums2的值为key，下一个比它大的值为value。然后遍历nums1，对应map中的值输出结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    let dic = new Map();
    for(let i=0;i<nums2.length;i++){
        for(let j=i+1;j<nums2.length;j++){
            if(nums2[j]>nums2[i]){
                dic[nums2[i]] = nums2[j];
                break;
            }
            if(j==nums2.length-1){
                dic[nums2[i]] = -1;
            }
        }
        if(i==nums2.length-1){
            dic[nums2[i]] = -1;
        }
    }
    let result = [];
    for(const i of nums1){
        result.push(dic[i])
    }
    return result;
};

2、单调栈+哈希表

利用单调栈+哈希表来快速确定每个元素右边第一个比它大的元素。

这个思路其实和第一种思路一样：先确定nums2中每个元素右边第一个比啊它大的元素，然后再通过哈希表进行筛选输出。这里时间节省在使用了单调栈。

具体使用方法如下：我们需要反向遍历nums2，这也符合栈的特点。接着我们需要判断当前值是否比现存栈顶元素大，如果大，则将栈顶元素出栈；反之，则不进行操作。循环以上操作，如果栈为空，也跳过该操作。最后将当前元素入栈。同时需要使用哈希表记录对应关系。

操作演示：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    let hmap = new Map();
    let stack = [];
    for(let i=nums2.length-1;i>=0;i--){
        let num = nums2[i];
        while(stack.length && num>stack[stack.length-1]){
            stack.pop();
        }
        hmap.set(num,stack.length ? stack[stack.length-1] : -1);
        stack.push(num);
    }
    let result = new Array(nums1.length).fill(0).map((_,i)=> hmap.get(nums1[i]));
    return result;
};