下一个更大元素 I

TIP

nums1 中数字 x 的 下一个更大元素 是指 x 在nums2中对应位置右侧的第一个比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。

思路

利用单调栈求出nums2下一个更大元素的值的数组
在两层循环遍历两个数组，寻找ans[]的摆放位置

var nextGreaterElement = function(nums1, nums2) {
    let ans = []
    let res = nextBigger(nums2)
    for(let i=0;i<nums1.length;i++){
        for(let j=0;j<nums2.length;j++){
            if(nums1[i]===nums2[j]){
                ans[i] = res[j]
            }
        }
    }
    return ans
};

// 利用单调栈求出nums2下一个更大元素的值的数组
var nextBigger = function(nums) {
    let res = Array(nums.length).fill(-1)
    let stack = []
    stack.push(0)
    for(let i=1;i<nums.length;i++){
        if(nums[i] > nums[stack[stack.length-1]]){
            while(nums[stack[stack.length-1]] < nums[i]){
                let top = stack.pop()
                res[top] = nums[i]
            }
        }
        stack.push(i)
    }
    return res
};

下一个更大元素 I ​

思路 ​

下一个更大元素 I

思路