每天一道力扣题：496. 下一个更大元素 I

题目

给定两个没有重复元素的数组 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。

复制代码

注意:

1. nums1和nums2中所有元素是唯一的。
2. nums1和nums2 的数组大小都不超过1000。

思路

单调栈+哈希map

/**
 * @desc 单调栈 +哈希map, 
 * 时间复杂度：O(M+N)，其中 M 和 N 分别是数组 nums1 和 nums2 的长度。因为我们两个循环。
 * 空间复杂度：O(N)。我们在遍历 nums2 时，需要使用栈，以及哈希映射用来临时存储答案。
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    if (Array.isArray(nums1) && Array.isArray(nums2)) {
        // 1. 遍历nusm2，找出nusm2中每个元素的下一个更大元素值，并将其映射关系存在哈希map
        // 2. 遍历时候比较规则：空栈时候元素入栈，后面元素与栈顶元素进行比较，如果后面元素一直大于栈顶元素，则出栈并在map存入对应映射关系，如果不大于则元素入栈
        // 3. 判断栈是否为空，非空【不存在下一个更大元素】遍历出栈内元素，设置对应映射关系存入map。
        // 4. 遍历nusm1，在map中返回对应映射关系
        const result = []
        const stack = []
        const map = new Map()
        for (let i = 0; i < nums2.length; i++) {
            if (!stack.length) {
                stack.push(nums2[i])
            } else {
                while (nums2[i] > stack[stack.length - 1]) {
                    map.set(stack.pop(), nums2[i])
                }
                stack.push(nums2[i])
            }
        }
        while(stack.length) {
            map.set(stack.pop(), -1)
        }
        for (let i = 0; i < nums1.length; i++) {
            result.push(map.get(nums1[i]))
        }
        return result
    }
};
复制代码

广告位

觉得有意思点个右下角在看，或者直接关注。