下一个更大元素 I

题目

题目来源：力扣（LeetCode）

给你两个 没有重复元素 的数组 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. 创建一个单调栈，一个哈希表，哈希表 存储 num2 中的数字及对应的下一个更大的数字的映射关系
2. 遍历 num2 中的每一个元素
3. 若当前栈无数据，则当前数字入栈备用。
4. 若当前栈有数据，则用当前数字与栈顶比较：
   1. 当前数字 > 栈顶，代表栈顶对应下一个更大的数字就是当前数字，则将该组数字对应关系，记录到哈希表。
   2. 当前数字 < 栈顶，当前数字压入栈，供后续数字判断使用。
5. 这样，我们就可以看到哈希表中存在部分 nums2 数字的对应关系了，而栈中留下的数字，代表无下一个更大的数字，我们全部赋值为 -1，然后存入哈希表即可。
6. 遍历 nums1，直接询问哈希表拿对应关系即可。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
 var nextGreaterElement = function(nums1, nums2) {
  // 存储 num2 中的数字及对应的下一个更大的数字的映射关系
  const map = new Map();
  const stack = [];
  const res = [];
  // 遍历 num2 中的每一个元素，找到它的右边第一个更大的元素，将其对应关系存放到 哈希表 中
  nums2.forEach(item => {
    // 当前数字 > 栈顶元素，代表栈顶对应下一个更大的数字就是当前数字，将该组数字对应关系，记录到哈希表
    while (stack.length && item > stack[stack.length - 1]) {
      map.set(stack.pop(), item);
    }
    // 当前数字 < 栈顶元素，当前数字压入栈，供后续数字判断使用
    stack.push(item);
  })
  // 栈中留下的数字，代表无下一个更大的数字，全部赋值为 −1 ，然后存入哈希表
  stack.forEach(item => map.set(item, -1));
  // 遍历 nums1，直接询问哈希表拿对应关
  nums1.forEach(item => res.push(map.get(item)))
  return res;
};