描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

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

示例

示例1：

  1. 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
  2. 输出: [-1,3,-1]
  3. 解释:
  4.     对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
  5.     对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
  6.     对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例2：

  1. 输入: nums1 = [2,4], nums2 = [1,2,3,4].
  2. 输出: [3,-1]
  3. 解释:
  4.     对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
  5.     对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示

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

解题思路

  • 遍历 nums2, 维护一个递减的单调栈。
  • 当前元素值大于栈顶元素时，找到栈顶元素右边第一个大于自己的元素，用 hashMap 存储。将栈顶元素出栈，重复这个过程，直到栈为空或者当前元素小于栈顶元素。将当前元素压栈。
  • 遍历 nums1, 然后更新结果数组的值 res[j] = map.getOrDefault(nums1[j], -1);

    代码

    1. class Solution {
    2.   public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    3.       int n = nums2.length;
    4.       int m = nums1.length;
    5.       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    6.       Deque<Integer> deque = new LinkedList<Integer>();
    7.       int[] res = new int[m];
    8.       for (int i = 0; i < n; i++) {
    9.           while (!deque.isEmpty() && nums2[i] > deque.peekLast()) {
    10.               map.put(deque.pollLast(), nums2[i]);
    11.           }
    12.           deque.addLast(nums2[i]);
    13.       }
    14.       for (int j = 0; j < m; j++) {
    15.           res[j] = map.getOrDefault(nums1[j], -1);
    16.       }
    17.       return res;
    18.   }
    19. }

    复杂度分析

时间复杂度：O(N+M)，分别遍历数组 nums1 和数组 nums2 各一次即可，对于 nums2 中的每个元素，进栈一次，出栈一次；
空间复杂度：O(N)。我们在遍历 nums2 时，需要使用栈，以及哈希映射用来临时存储答案。