LeetCode 496. 下一个更大元素 I

2025-09-16 HGNULB 约 10 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 496. 下一个更大元素 I

题意分析

给两个数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对 nums1 中的每个数字 x，先在 nums2 中找到它所在的位置，然后从这个位置向右找出第一个比 x 大的数字并返回；如果右边没有任何比它大的数，就返回 -1。答案按 nums1 的顺序组织成数组返回。

这道题的第一层信息是问题域的转移：nums1 只负责决定「问哪些数、按什么顺序问」，所有的位置关系、右侧关系都发生在 nums2 里。nums1 自身的下标顺序和相邻关系完全没有意义，把它当成一张查询清单就对了。所以真正要解决的问题是：对 nums2 的每个元素，求出它右侧第一个更大的元素。求完之后 nums1 只是逐个查表。

第二层信息藏在「所有整数互不相同」这个约束里。元素唯一意味着值本身就能当唯一标识，我们可以用「值 → 答案」的哈希表来承接预处理结果，而不必绕道下标。如果题目允许重复值，这条捷径立刻失效，就必须在 nums1 里先定位下标。这也是它比 503、739 简单的地方。

第三层信息来自「右侧第一个更大」这个措辞。它同时含有两个限定：方向是单向向右，条件是严格大于，且只要最近的那一个。「最近」这个词决定了答案不能通过维护全局最值来求——右边有个更大的数并不代表它就是答案，中间可能还夹着一个更小但依然大于当前值的数。

边界：nums2 的最后一个元素右侧为空，答案必然是 -1；nums2 中的最大值右侧不可能有更大的数，答案也是 -1；nums1 长度可以等于 nums2 长度，即整个数组都要问一遍。数据规模很小（两个数组长度都不超过 1000），$O(mn)$ 的暴力其实能通过，但面试问的显然不是能不能过。

解法：单调递减栈预处理 nums2

核心思路

暴力解法非常自然：对 nums1 的每个数，先在 nums2 里线性找到它的位置，再从该位置往右扫直到遇见更大的数。这是 $O(mn)$ 的，数据小的时候能过。瓶颈在于大量重复扫描——如果 nums2 是 [5, 4, 3, 2, 1, 9]，为了给前面五个数各找一次答案，末尾那个 9 会被反复扫到，前四段路径几乎完全重叠。

换个角度想：与其站在每个元素的立场上「向右找答案」，不如站在每个新元素的立场上「向左送答案」。从左到右扫描 nums2，当读到一个新数字 num 时，它天然就是它左边所有元素的右侧候选。而对左边某个还没拿到答案的数 v，如果 v < num，那么 num 一定就是 v 的答案——因为 num 是从 v 出发向右遇到的第一个大于它的数（v 和 num 之间的元素全都没能满足 v，否则 v 早就出局了）。

关键在于要维护「左边还欠着答案」的那些元素，而且要能快速找出其中所有小于 num 的。这里有一个决定性的观察：如果两个待定元素 a 在左、b 在右且 a < b，那么 a 永远不可能先于 b 拿到答案——任何能让 a 出局的数必然也大于 b，会先让 b 出局。所以待定集合中，靠左的元素必然大于等于靠右的元素，它天然是一个从栈底到栈顶单调递减的序列。既然如此，用一个栈存它就够了，需要出局的元素永远聚集在栈顶那一段。

由此确立循环不变量：读完 nums2 的前 i 个元素后，栈中自底向上保存的恰好是这 i 个元素中「右侧尚未出现更大元素」的那些，且它们的值严格递减、在原数组中的位置从左到右递增；已经确定答案的元素全部已写入哈希表 nextGreater。

每读入一个 num，就不断弹出栈顶所有小于 num 的元素并把它们的答案记为 num，直到栈顶不再小于 num（此时 num 也帮不了更深的元素了，因为下面的元素只会更大），然后把 num 自己压栈成为新的待定者。扫描结束后仍留在栈里的元素，就是那些右侧再无更大值的，它们在哈希表中查不到，取默认值 -1 即可——不需要在结尾专门清空栈补 -1，让查询端兜底更简洁。

解题步骤

准备哈希表 nextGreater 与一个栈：哈希表的键是元素值而不是下标，这一步的合法性完全依赖「元素互不相同」这个约束，写之前应该在心里确认一遍。

从左到右遍历 nums2：方向必须是从左往右。因为「送答案」的逻辑要求新元素在旧元素的右侧，反向遍历求出来的会是「左侧第一个更大元素」。

内层 while 循环：栈非空且栈顶 < num 时，弹出栈顶并记录 nextGreater[栈顶] = num。用 while 而不是 if，是因为一个较大的新元素可能一次性解决掉栈顶连续的一整段；写成 if 只会结算最近的一个，剩下的元素会被后面压入的更小值挡住，答案错成 -1。判断条件用严格小于（stack.peek() < num）：本题元素互不相同，用 <= 也能跑对，但严格小于才准确表达「下一个更大元素」的语义，迁移到允许重复值的题目时才不会出错。

循环结束后把 num 压栈：入栈动作必须在弹栈之后，否则会拿自己和自己比较。此时栈的单调递减性质刚好被维持——栈顶要么为空，要么大于 num。

遍历 nums1 逐个查表，查不到填 -1：查不到意味着该元素在扫描结束时仍滞留栈中，也就是右侧不存在更大值。Java 里用 getOrDefault(nums1[i], -1)，Go 里用 val, exists := m[num] 的双返回值判断，都比先补 -1 再查更直接。

以 nums1 = [4, 1, 2]、nums2 = [1, 3, 4, 2] 走一遍（期望 [-1, 3, -1]）。先做预处理，逐个读入 nums2 的元素，每轮列出「弹栈结算 → 入栈 → 栈内容（左为底）→ 哈希表」。

读入 1：栈为空，无可结算，压入 1。栈 [1]，哈希表 {}。

读入 3：栈顶 1 < 3，弹出并记录 1 → 3；栈空，弹栈结束；压入 3。栈 [3]，哈希表 {1: 3}。

读入 4：栈顶 3 < 4，弹出并记录 3 → 4；栈空，结束；压入 4。栈 [4]，哈希表 {1: 3, 3: 4}。

读入 2：栈顶 4 不小于 2，一次都不弹；压入 2。栈 [4, 2]，哈希表 {1: 3, 3: 4}。注意此刻栈自底向上是 4, 2，正好递减，符合不变量。

扫描结束，栈中残留 4 和 2，它们右侧确实没有更大的元素，哈希表里没有它们的键。

再按 nums1 查表：4 不在表中，填 -1；1 查到 3；2 不在表中，填 -1。返回 [-1, 3, -1]，与期望一致。

顺带看一下 while 写成 if 会发生什么：把 nums2 换成 [3, 2, 5]，读入 5 时栈是 [3, 2]，while 会连弹两次得到 2 → 5 和 3 → 5；而 if 只结算一次 2 → 5，然后把 5 压在 3 上面，3 的答案永远丢失，最终被填成 -1。

代码实现

class Solution {
    // 从左到右扫描 nums2，单调递减栈保存尚未找到下一个更大元素的数字。
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreater.getOrDefault(nums1[i], -1);
        }

        return res;
    }
}

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // 从左到右扫描 nums2，单调递减栈保存尚未找到下一个更大元素的数字。
    nextGreater := make(map[int]int)
    stack := make([]int, 0)
    for _, num := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < num {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreater[top] = num
        }
        stack = append(stack, num)
    }

    res := make([]int, len(nums1))
    for i, num := range nums1 {
        if val, exists := nextGreater[num]; exists {
            res[i] = val
        } else {
            res[i] = -1
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(m + n)$，其中 n 是 nums2 的长度、m 是 nums1 的长度。凭什么：虽然有嵌套的 while，但 nums2 的每个元素至多入栈一次、出栈一次，弹栈总次数被 n 摊还封顶，所以预处理是 $O(n)$ 而不是 $O(n^2)$；第二段是对 nums1 的一次遍历，每次哈希查询均摊 $O(1)$，合计 $O(m)$。

空间复杂度：$O(n)$（不计返回值）。凭什么：栈最多同时装下 nums2 的全部元素（当 nums2 严格递减时），哈希表最多存 n 条映射，两者都与 nums2 的长度同阶。这是用空间换掉暴力那层重复扫描的代价。

关键点总结

当查询集合是数据集合的子集时，先把完整数据集预处理成一张答案表，再让查询端 $O(1)$ 查表，是把 $O(mn)$ 降到 $O(m + n)$ 的通用套路；识别出「nums1 只是查询清单」是本题的第一步。

「右侧第一个满足某比较关系的元素」这类问题的统一答案是单调栈：把视角从「向右找」翻转成「新元素向左送」，需要结算的元素永远聚在栈顶。

单调性不是硬性维护出来的，而是推导出来的必然结果——左边较小的待定元素一定不会比右边较大的先出局，所以待定集合天然递减。面试时能讲出这层推导，比背「用单调栈」高一个层次。

摊还分析是单调栈的复杂度命门：看到嵌套循环先别慌，只要能论证「每个元素至多进出各一次」，总复杂度就是线性的，这句话应该主动说给面试官听。

用值当哈希键的前提是元素唯一，这是本题独有的简化；一旦允许重复就必须改用下标建表，这也是面试官最常见的追问方向。

扫描结束后栈里的残留元素就是「无解」的那批，交给查询时的默认值兜底比事后补 -1 更省事，这个收尾习惯在 739、503 里同样适用。

易错点总结

内层弹栈写成 if 而不是 while：nums2 = [3, 2, 5] 时读入 5 只结算掉 2，3 被永久压在栈底，最终 nums1 里查 3 得到 -1，正确答案是 5。

先压栈再弹栈：num 刚入栈就成了栈顶，stack.peek() < num 用自己和自己比较恒为假，整个哈希表最后是空的，所有答案都是 -1。

遍历方向反过来，从右往左扫 nums2：[1, 3, 4, 2] 求出的是「左侧第一个更大元素」，查 1 会得到 -1 而不是 3。

把 nums1 拿来建栈或参与单调性维护：nums1 = [4, 1, 2] 的相邻关系在原数组里根本不相邻，用它做扫描会得出毫无意义的结果。

弹栈时把 nextGreater 的键值写反，记成 nextGreater[num] = 栈顶：[1, 3] 会记成 3 → 1，查 1 时得到 -1、查 3 时得到比它小的 1，方向整个颠倒。

扫描结束后忘了处理栈中残留，且查表时没有默认值：Java 里用 map.get(nums1[i]) 直接赋给 int，nums1 含 nums2 的最大值时返回 null，自动拆箱抛空指针异常。

Go 里写成 res[i] = nextGreater[num] 不判断存在性：map 取不到键返回零值 0，nums2 = [2, 1] 查 2 会得到 0 而不是 -1，恰好和某些合法元素值混淆。

Go 弹栈时先截断切片再取栈顶：stack = stack[:len(stack)-1] 之后再读 stack[len(stack)-1] 拿到的是次栈顶，[3, 2, 5] 会把 3 的答案错记到 2 头上。

返回数组的长度按 nums2.length 开：nums1 = [4]、nums2 = [1, 3, 4, 2] 会返回长度 4 的数组，后三位是没被赋值的 0，判题直接失败。

误以为栈里应该存下标：本题元素唯一、也不需要计算距离，存值最简；但如果照搬 739 的模板存下标又忘了在建表时转回值，哈希表的键就成了下标，查询全部落空。

相似题目

题目	难度	考察点
739. 每日温度	中等	要的是距离而不是值，栈里必须存下标，且不再有 `nums1` 这层查询映射
503. 下一个更大元素 II	中等	数组变成循环的，需遍历两轮或对 `2n` 取模，且允许重复值，只能按下标建表
901. 股票价格跨度	中等	数据流在线到达，栈要作为对象成员长期存活，求的是左侧连续不超过当前值的长度
907. 子数组的最小值之和	中等	单调递增栈求每个元素作为最小值的左右边界，还要处理相等元素的重复计数
84. 柱状图中最大的矩形	困难	同时需要左右两侧第一个更小元素，通常配合哨兵把边界情况并入主循环
42. 接雨水	困难	弹栈时要按「左墙、底、右墙」三者结算横向水量，不是简单记录一个答案值
402. 移掉 K 位数字	中等	单调栈用于构造字典序最小结果，弹栈受剩余次数 `k` 限制，还要处理前导零
1019. 链表中的下一个更大节点	中等	载体是链表无法随机访问，需先转数组或边遍历边用栈存下标
LCR 038. 每日温度	中等	与 739 同题，可直接套用存下标的模板