LC 496. 下一个更大元素 I

题目描述

这是 LeetCode 上的 496. 下一个更大元素 I ，难度为 简单。

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

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

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

示例 1:

1
2
3
4
5
6
7
8
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

输出: [-1,3,-1]

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

示例 2:
1
2
3
4
5
6
7
输入: nums1 = [2,4], nums2 = [1,2,3,4].

输出: [3,-1]

解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示：

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

模拟

一个朴素的做法是直接根据题意进行模拟，对于每个 $ans[i]$ 而言，先找到 $nums1[i]$ 在 $nums2$ 的位置 $j$，然后接着往后找到最近一个比其大的数，如果 $j$ 走到结尾尚未出现合法的 $ans[i]$，则是 $-1$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int j = 0;
            while (j < m && nums1[i] != nums2[j]) j++;
            while (j < m && nums1[i] >= nums2[j]) j++;
            ans[i] = j < m ? nums2[j] : -1;
        }
        return ans;
    }
}

  • 时间复杂度：$O(n * m)$
  • 空间复杂度：$O(n)$

单调栈

当题目出现「找到最近一个比其大的元素」的字眼时，自然会想到「单调栈」。

具体的，由于我们目标是找到某个数其在 $nums2$ 的右边中第一个比其大的数，因此我们可以对 $nums2$ 进行逆序遍历。

我们在遍历 $nums2$ 时，实时维护一个单调栈，当我们遍历到元素 $nums2[i]$ 时，可以先将栈顶中比 $nums2[i]$ 小的元素出栈，最终结果有两种可能：

  1. 栈为空，说明 $nums2[i]$ 之前（右边）没有比其大的数；

  2. 栈不为空， 此时栈顶元素为 $nums2[i]$ 在 $nums2$ 中（右边）最近的比其大的数。

再利用数组中数值各不相同，在遍历 $nums2$ 的同时，使用哈希表记录每个 $nums2[i]$ 对应目标值是多少即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        Deque<Integer> d = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = m - 1; i >= 0; i--) {
            int x = nums2[i];
            while (!d.isEmpty() && d.peekLast() <= x) d.pollLast();
            map.put(x, d.isEmpty() ? -1 : d.peekLast());
            d.addLast(x);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = map.get(nums1[i]);
        return ans;
    }
}

  • 时间复杂度：维护单调栈，每个元素最多入栈出栈一次，复杂度为 $O(m)$；构造答案复杂度为 $O(n)$。整体复杂度为 $O(n + m)$
  • 空间复杂度：$O(m)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.496 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。