LC496. 下一个更大元素 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 。

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

题目解析

题目在说什么

我们有两个数组：nums1 和 nums2。nums1 是 nums2 的一个子集，意思是 nums1 里的所有数字在 nums2 里都能找到。而且这两个数组里都没有重复的数字。

现在我们要对 nums1 里的每个数字，在 nums2 里找到它右边第一个比它大的数字。如果右边没有比它大的，答案就是 -1。

比如：

• nums1 = [4,1,2]，nums2 = [1,3,4,2]
• 对于数字 4：它在 nums2 里是第3个，右边只有 2，没有比 4 大的，所以答案是 -1。
• 对于数字 1：它在 nums2 里是第1个，右边第一个比它大的是 3，所以答案是 3。
• 对于数字 2：它在 nums2 里是最后一个，右边没有数字，答案是 -1。

最终输出就是 [-1, 3, -1]。

---

思路是怎么来的

想象你在一排人里找自己右边第一个比自己高的人。你站在队伍里，每个人都有一个身高数值。你要找的是：在你右边，第一个比你高的人。

如果你从左往右看，每个人都要往后看，很麻烦，因为你要记住后面所有人的身高。但如果你从右往左看，就简单多了：你只需要记住你已经看过的人里，谁是最高的（而且离你最近）。这样你就能很快知道右边第一个比你高的是谁。

这个“记住”的过程，可以用一个栈来实现。栈就像一个竖着的桶，你只能从上面放东西和拿东西。我们让栈里的数字从下到上越来越小（也就是栈顶最小）。这样，当你从右往左看一个新数字时，你只需要把栈里比它小的都扔掉（因为它们不可能成为它左边任何数字的“右边第一个更大”），剩下的栈顶就是它右边第一个更大的数字。

这就是单调栈的思路：维护一个单调递增（从栈底到栈顶越来越大）的栈，用来快速找到右边第一个更大的元素。

---

代码逐步拆解

我们来看参考代码，一行一行解释它在干什么。

Map<Integer, Integer> res = new HashMap<>();
Stack<Integer> stack = new Stack<>();

• res 是一个哈希表（字典），用来存每个数字的“下一个更大元素”。比如 res[1] = 3 表示数字1的下一个更大元素是3。
• stack 是一个栈，用来帮助我们找到右边第一个更大的数字。

for (int i = nums2.length - 1; i >= 0; --i) {
    int num = nums2[i];

• 我们从 nums2 的最后一个数字开始往前看（从右向左）。这样我们就能保证栈里存的是当前数字右边的所有数字。

    while (!stack.isEmpty() && num >= stack.peek()) {
        stack.pop();
    }

• 这一步是“清理”栈：只要栈不为空，并且当前数字 num 比栈顶的数字大或相等，就把栈顶扔掉。
• 为什么要扔掉？因为栈顶比 num 小，它就不可能成为 num 左边任何数字的“右边第一个更大”了（因为 num 更大，而且更靠左，所以对于更左边的数字来说，num 才是更近的更大数字）。
• 注意：题目说“下一个更大元素”是严格大于，所以相等也要扔掉。

    res.put(num, stack.isEmpty() ? -1 : stack.peek());
    stack.push(num);