每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

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] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。

2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。

4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

代码卡片

题目解析

这个问题要求找到数组 nums1 中每个元素在数组 nums2 中的下一个更大元素。题目提供了两个数组 nums1 和 nums2，并且 nums1 是 nums2 的子集。我们需要遍历 nums1 中的每个元素，找到它在 nums2 中的位置，然后从该位置开始寻找第一个比它大的元素。如果找不到更大的元素，则返回 -1。

方法一：暴力解法

对于 nums1 中的每一个元素，首先找到它在 nums2 中的对应位置。
从该位置开始向右遍历 nums2，寻找第一个比当前元素大的数。
如果找到，记录下这个数；如果找不到，记录为 -1。

这种方法的时间复杂度是 O(nums1.length * nums2.length)，适用于小规模的输入。

时间复杂度：O(nums1.length * nums2.length)。对于 nums1 中的每一个元素，我们都需要在 nums2 中进行一次遍历。
空间复杂度：O(1)，除了存储结果的数组外，不需要额外的空间。

var nextGreaterElement = function (nums1, nums2) {
    const ans = [];
    for (let num of nums1) {
        let found = false;
        let greater = -1;
        for (let i = nums2.indexOf(num) + 1; i < nums2.length; i++) {
            if (nums2[i] > num) {
                greater = nums2[i];
                break;
            }
        }
        ans.push(greater);
    }
    return ans;
}

方法二：使用单调栈的优化方法

具体来说：

从右往左遍历 nums2，使用栈来记录可能的下一个更大元素。
对于每个元素，如果栈顶元素小于等于当前元素，则弹出栈顶，直到找到一个比当前元素大的元素或栈为空。
记录当前元素的下一个更大元素（如果存在）。
然后处理 nums1 中的元素，直接查找预处理后的结果。

时间复杂度：O(nums1.length + nums2.length)。遍历 nums2 是 O(nums2.length)，构建结果数组是 O(nums1.length)。
空间复杂度：O(nums2.length)，用于存储栈和哈希映射。

var nextGreaterElement = function (nums1, nums2) {
    const nextGreaterMap = new Map();
    const stack = [];

    for (let i = nums2.length - 1; i >= 0; i--) {
        const num = nums2[i];
        while (stack.length > 0 && stack[stack.length - 1] <= num) {
            stack.pop();
        }
        nextGreaterMap.set(num, stack.length > 0 ? stack[stack.length - 1] : -1);
        stack.push(num);
    }

    return nums1.map(num => nextGreaterMap.get(num));
}