Leetcode 496.下一个更大元素I

题目要求

  • 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 。

单调栈

  • 因为nums1是nums2的子集，所以只需要对nums2使用单调栈，然后判断该元素是否在nums1中，如果在，则将结果存入res中即可。
  • 需要注意的是需要使用map来存储nums1中每个元素对应的下标，方便将结果存入res中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
      int[] res = new int[nums1.length];
        Arrays.fill(res, -1);

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }

        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);

        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[stack.peek()]) {
                stack.push(i);
            }else {
                while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                    // 当发现当前元素大于栈顶元素时，判断栈顶元素是否在nums1中，如果在，则将结果存入res中
                    if (hashMap.containsKey(nums2[stack.peek()])) {
                        int idx = hashMap.get(nums2[stack.peek()]);
                        res[idx] = nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return res;  
    }
}