496. 下一个更大元素 I

[pigpigever]

题目剖析

题目描述

给定两个没有重复元素的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

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

解题思路

这道题利用 HashMap 可以解决，但是思路其实有两种：

1. 暴力法，直接利用 nums2 生成 值 和 key 的 HashMap，然后遍历 nums1 来找下一个更大的元素
2. 利用 nums2 来生成下一个更大元素的 HashMap，然后遍历 nums1 即可得到结果

示例代码

暴力法

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const map = new Map()
    const ans = []
    for (let i = 0; i < nums2.length; i++) {
        map.set(nums2[i], i)
    }
    for (const num of nums1) {
        const targetIndex = map.get(num)
        let flag = 0
        for (let i = targetIndex + 1; i < nums2.length; i++) {
            if (num < nums2[i]) {
                flag = i
                break
            }
        }
        ans.push(flag ? nums2[flag] : -1)
    }
    return ans
};

利用栈来解决

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const stack = [], map = new Map()
    for (const num of nums2) {
        while (stack.length && num > stack[0]) {
            map.set(stack.shift(), num)
        }
        stack.unshift(num)
    }
    while (stack.length) {
        map.set(stack.shift(), -1)
    }
    return nums1.map((num) => map.get(num))
};