LeetCode 496：单调栈与哈希表求解下一个更大元素

这份LeetCode刷题记录的主角是第496题——下一个更大元素 I。第一次看到这题的名字，你可能觉得它在绕口令，其实它问的事情很朴素：给你两个数组nums1和nums2，nums1是nums2的子集，对nums1中的每个元素，去nums2里找到它在哪个位置，然后看这个位置右边有没有比它更大的数，有就返回那个数，没有就返回-1。

这个题适合谁练？如果你刚结束数组和哈希表专题，正琢磨着怎么入门栈和单调栈，它几乎是绕不开的第一课。为什么这么说，因为题目表面上是数组遍历，实际考的是你能不能想到用单调栈去预处理nums2，再配合一张哈希表快速回答nums1里的每一个查询。而且这题的难度标着“简单”，门槛低，但背后的“下一个更大元素”模型一点不简单，它会一直延伸成一整个中等题系列。

接下来我按自己的刷题顺序来写：先讲最直觉的暴力解法，再拆单调栈为什么是正解，然后给一份可以直接抄的代码和注释，最后把调试时踩过的坑以及我如何用这题举一反三都交代一遍。整个节奏就按我从“读题都费劲”到“闭眼默写模板”的真实路径来，你看完应该能少走不少弯路。

1. 先别急着写代码：把题意和暴力解彻底聊透

1.1 题干里的三个信息点

这道题给的条件有三个关键点，很多人刷题上来就写代码，把这三个点忽略掉，后面容易出错。

第一个点，nums1是nums2的子集。这句话决定了nums1里不会出现nums2中不存在的元素，而且两个数组里都没有重复元素。没有重复元素这件事非常关键，它意味着我们可以放心地用元素值作为哈希表的键，也可以放心地在单调栈里存元素值而不是下标。我在第4节会详细说存值和存下标的区别，这里先记住：无重复是题目给的“优惠条件”。

第二个点，我们要找的是“下一个更大元素”，也就是在nums2中那个元素位置的右侧，找到第一个比它大的数。“第一个”三个字很重要，它不是找最大的那个，也不是右侧所有比它大的数，而是离它最近的、严格大于它的数。如果位置右侧根本没有比它大的数，结果就是-1。

第三个点，最终答案的顺序要跟着nums1走，不是跟着nums2走。所以输出数组的长度等于nums1的长度，第i位存的是nums1[i]的答案。很多初学者在这里犯迷糊：先遍历nums2算了一堆结果，最后不知道按什么顺序填答案了。

把这三个信息点放在一起，题目其实可以翻译成一句大白话：给了一张“成绩排名表”nums2，另有一串要查询的学生名单nums1，每次查某个学生，就在排名表里找到他，然后往后看，看有没有比他排名更靠前（数字更大）的，有就返回第一个，没有返回-1。

1.2 暴力解法：怎么写、为什么能过、又为什么不够好

最朴素的想法是直接照题干模拟。我先把代码写出来，这个版本的代码几乎不会写错，适合作为理解题意的锚点。

python复制def nextGreaterElement(nums1, nums2):
    res = []
    for x in nums1:
        # 第一步：在nums2中定位x
        idx = nums2.index(x)
        # 第二步：从idx+1向右扫描，找第一个大于x的数
        ans = -1
        for j in range(idx + 1, len(nums2)):
            if nums2[j] > x:
                ans = nums2[j]
                break
        res.append(ans)
    return res

Java版本也顺手给一版，思路完全一致：

java复制public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        int ans = -1;
        boolean found = false;
        for (int j = 0; j < nums2.length; j++) {
            if (nums2[j] == nums1[i]) {
                found = true;
            }
            if (found && nums2[j] > nums1[i]) {
                ans = nums2[j];
                break;
            }
        }
        res[i] = ans;
    }
    return res;
}

暴力解的时间复杂度是O(mn)，m是nums1的长度，n是nums2的长度。为什么是这个量级？因为对nums1中每个元素，都要先在nums2里做一次线性查找，运气差的话还要一直扫到数组末尾才能找到或者确定没有。两个循环嵌套起来，最坏情况就是m乘n。空间复杂度是O(1)，不算答案数组的话，只用了几个临时变量。

在某些平台的数据规模下，这题的数据量不算大，暴力解法也能通过。但真实面试中，如果考官把这题的数据范围放大到10的5次方级别，暴力解就彻底扛不住了。我见过不少能写出暴力解的人，但被问一句“能不能优化到线性时间”就直接卡住。所以暴力解只能作为理解题意的跳板，不是最终答案。

这里有一个很反直觉的点：暴力解明明是把“定位”和“找更大”两件事分开做的，整体复杂度是m乘n；但如果反过来，先花O(n)的时间把nums2处理成一张“答案表”，再用O(m)的时间去查表，总复杂度立刻变成O(n+m)。这中间的差距，就是哈希表和单调栈带来的。下面一节正式把这两种工具请上场。

2. 正解登场：单调栈加哈希表，为什么这是一对黄金搭档

2.1 单调栈到底在做什么：一个排队找高个子的例子

先不急着写代码，我用一个生活化的场景把单调栈讲明白。

想象操场上有一排人排队，从左到右依次是身高1、3、4、2的人，对应nums2 = [1,3,4,2]。规则是：每个人只能往后看，找身后第一个比自己高的人，找到了就记住他的身高，找不到就算-1。请问每个人的答案是什么？

如果从前往后一个个往后看，每个人都要往后蹭好久，很累。单调栈的做法是让这排人从左往右依次“报到”，但已经报到的人站成一队，队形始终保持从低到高排列。具体模拟一遍：队伍是空的，左边第一个人身高1先入队。第二个人身高3来了，他比队尾的1高，好了，1往后看，身后第一个比自己高的就是3，1的答案记下并离开队伍，3站到队尾。第三个人身高4来了，他比队尾的3还高，3的答案就是4，3离开，4站到队尾。第四个人身高2来了，2比队尾的4矮，2直接站到队尾。到此队伍结束，队伍里剩下4和2。这两个人往后看，没有比他们更高的人了，答案都是-1。

这个过程的精妙之处在于：每个人最多入队一次、出队一次，整个流程是线性的。队伍里始终保持着从队尾到队头身高递减的状态，这就是“单调栈”——准确说是单调递减栈。新来一个元素时，只要是比栈顶大，就说明栈顶的下一个更大元素找到了，栈顶出栈；比栈顶小，就入栈等着后面的人来解决它。

为什么栈内是递减的？因为只要发现新来的元素比栈顶大，栈顶就立刻出栈走人了，所以栈里永远只留着那些“还没找到答案”的元素，而它们只能按从高到低的顺序叠着。新来的元素如果不够高，就只能入栈，把自己压在上面。

我用一个表格把刚才的模拟记录一下，方便对照：

2.2 哈希表在这里承担什么角色：预处理一次，回答所有查询

单调栈把nums2扫描一遍之后，我们能得到所有“找到了下一个更大元素”的记录，也就是刚才模拟里那些出栈瞬间的配对：1→3，3→4。但还剩4和2没有记录，它们的答案是-1。

问题来了：这些记录最终要给nums1用，而nums1是乱序的，不是按nums2原序排的。怎么快速回答“nums1里这个元素x的答案是什么”？最直接的办法就是把这些配对放进一张哈希表，key是元素值，value是它的下一个更大元素。查nums1的时候，遍历一次，每次O(1)查表，查到就返回，查不到就返回-1。

哈希表在这里解决的其实是一类很常见的问题模式：“预处理一遍所有数据，然后回答大量单点查询”。类似的情况还有先统计词频再回答“某个单词出现几次”的题目。这类题的核心思想都是空间换时间，把重复计算的代价变成一张查表。

有一个细节值得特别注意：遍历完nums2后，栈里剩下的元素，比如刚才的4和2，不用专门在哈希表里存key对应-1。为什么？因为查询时可以直接用getOrDefault，Java里是map.getOrDefault(x, -1)，Python里是dict.get(x, -1)，查不到就返回-1。这样既省代码又省时间，是这题写法上一个很讨巧的地方。

还有同学会问：如果不用哈希表，而是每次都去nums2里用单调栈现场算，行不行？理论上行，但复杂度退化成了对nums1每个元素都跑一遍单调栈，又回到O(mn)了。所以先预处理nums2生成哈希表，再查nums1，这几乎是最优的解题路线。核心公式就一句话：单调栈负责O(n)预处理答案表，哈希表负责O(1)回答每个问题。

3. 手把手写代码：从框架到边界，每个细节都讲清楚

3.1 两种主流语言的完整实现与逐行注释

直接给出可以抄作业的版本。我用Python和Java各写一份，两份逻辑完全一致，你熟悉哪个就看哪个。

python复制class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 单调栈 + 哈希表
        stack = []                # 栈中存元素值，栈底到栈顶递减
        next_greater = {}         # key: nums2中的元素, value: 下一个更大元素

        # 第一遍：遍历nums2，用单调栈求出每个元素的下一个更大元素
        for num in nums2:
            # 新元素比栈顶大时，栈顶的下一个更大元素就是num
            # 用while因为栈里可能连续多个都比num小，要一次性全部出栈结算
            while stack and num > stack[-1]:
                next_greater[stack.pop()] = num
            stack.append(num)

        # 第二遍：遍历nums1，查表得到答案，查不到就说明没有更大元素，返回-1
        return [next_greater.get(num, -1) for num in nums1]

java复制class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            // 新元素比栈顶大，出栈结算
            while (!stack.isEmpty() && num > stack.peek()) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

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

下面把这些代码里最容易写成“看起来对但实际错”的细节一个个拆开讲。

第一个细节：为什么内层是while而不是if。这是很多人第一次写单调栈必踩的坑。如果写成if，推进到nums2 = [1, 2, 3]时，处理到3时栈里有[1,2]，if只能让2出栈去结算（2→3），1还压在上面等着，可1的答案明明也应该是3。只有用while，才能在num=3时连续把1和2都结算掉。记住一句话：新元素要比栈顶大，但栈底下可能还压着更小的元素，它们都该被这个新元素一起结算。

第二个细节：栈里存的是值，不是下标。题目保证nums2里没有重复元素，值可以直接当身份标识，查哈希表、入栈出栈都方便。但这个选择不是白捡的便宜，它建立在一个前提上：数组无重复。一旦遇到有重复元素的变体题，你必须改成存下标，否则值相同就分不清谁是谁了。这个问题我在第4节会专门讲。

第三个细节：Java里用Deque作为栈实现，而不是Stack。Stack这个类从Java早期就存在，但它继承自Vector，所有操作方法都加了同步锁，在高并发的场景下性能不占优。写算法题虽然不差这点性能，但ArrayDeque作为官方推荐的“栈实现”，语义更清晰，push和pop方法也更顺手。很多面试官看到你还在用Stack，可能会追问一句“知道为什么不用它吗”。

第四个细节：答案数组直接初始化为-1还是用getOrDefault，两种都可以，但getOrDefault更简洁。当然，如果你坚持在哈希表初始化时就把栈里剩余元素的-1存好，代码会多几行，逻辑上也讲得通。这个属于个人风格，唯一建议是别两种写法混在一起，面试时思路要统一。

3.2 时空复杂度计算与边界条件逐个验证

先算复杂度。遍历nums2时，每个元素入栈一次、出栈最多一次，所以while循环总的执行次数是O(n)，不是O(n²)。这里很多初学者会算错，看到while嵌套for就认为复杂度是平方级，其实内层while在整个遍历过程中累计最多执行n次。因此第一遍预处理是O(n)，第二遍查nums1是O(m)，总时间复杂度O(n+m)。

空间复杂度：栈最多入n个元素，哈希表最多存n个键值对，所以是O(n)。这个空间开销在面试里是可以接受的，毕竟题目给定的两个数组本身就有O(n)级别的输入。

边界条件我建议上机前先脑内过一遍：

空数组：如果nums1为空，代码第二遍遍历直接返回空数组，没问题。如果nums2为空，由于nums1是它的子集，nums1也必空，遍历nums2那一层也不会进循环，最终返回空数组，没毛病。

nums2是严格递减数组，比如[5,4,3,2,1]：遍历过程中任何新元素都不会大于栈顶，因为后面出现的数一个比一个小，所以没有一个元素出栈，哈希表始终是空的。查询nums1时，所有元素都查不到，全部返回-1。这符合题意。

nums2是严格递增数组，比如[1,2,3,4]：处理到2时，1出栈记下1→2；处理到3时，2出栈记下2→3；处理到4时，3出栈记下3→4。最后栈里只剩下4，哈希表里存了三个键值对。nums1随便怎么查，都能一击命中。递增数组是单调栈最“忙”的情况，出栈操作最多。

还有一个容易被忽略的细节：判断条件里用大于还是大于等于。本题数组无重复，用哪都一样；但如果把这道题改造成有重复值的场景，同时题意要求找“严格大于”的下一个元素，那就必须用大于，因为等于的元素不能算作更大。这个点我在改造变体题时会再提到。

4. 刷题过程中的坑与排查心得：那些文档里不会写的事

4.1 常见错误速查表：从编译错误到逻辑错误

这题因为代码短，编译期错误不多，但逻辑上的坑一个比一个隐蔽。我按自己带人刷题时见过的真实错误，整理成一张速查表：

这里面最让我印象深刻的是“答案顺序对不上”这个错。有个学弟写了很久的代码，逻辑看起来完全对，但输出数组顺序始终和nums1对不上。原因是他先把nums2从头到尾遍历，每遇到一个nums1中存在的元素，就想办法当场把答案填进res，但nums2的遍历顺序和nums1的答案顺序根本是两回事。正确的姿势永远是：先把nums2的结果全部算好存进哈希表，再按nums1的顺序逐位查表。这句话建议抄在笔记本上，能省下不少调试时间。

4.2 调试这个题的三板斧：打印、对拍、构造极端用例

我在自己做这题时，调试用了三个很土但很有效的办法，推荐你也试试。

第一板斧是把每一步的栈内容打印出来。代码里在for循环内加一行print(stack)，运行一个小用例nums2 = [1,3,4,2]，你就能看到栈从空变为[1]、[3]、[4]、再到[4,2]的变化过程。这个打印过程能让你直观感受到“哪个瞬间哪个元素结算了”。

第二板斧是对拍。写一个绝对正确的暴力解，然后用随机小数组反复测试两份代码的结果是否一致。对拍在算法竞赛里是家常便饭，写业务代码的同学可能不熟悉，但对单调栈这种“过程抽象”的题型，对拍几乎是排查逻辑错误的最快途径。我通常用Python快速写暴力解，然后生成几十组随机用例对比。

第三板斧是构造极端用例。针对这题，我建议至少测四组：nums2单调递增、nums2单调递减、nums2只有一个元素、nums1只有一个元素。每一种场景都会逼出不同的问题。比如nums2只有一个元素时，哈希表必然是空的，这时候如果忘记用getOrDefault，就很容易返回null或者默认值，从而报错。

还有一个经验想单独说：面试时如果让你现场做这题，不要一上来就写单调栈。先用一句话说“我可以先讲暴力解，复杂度O(mn)，然后再优化”，这个顺序本身就在向面试官展示你的思考过程。写完单调栈解法后，主动提一句“每个元素最多进出栈一次，所以虽然看着像嵌套循环，但复杂度是线性的”。很多面试官对这个点很敏感，你主动说破比等他来问你强得多。

5. 举一反三：一个模板吃透“下一个更大元素”整条题目线

5.1 从496到739、503、42：同一套模板的花式用法

做完496这一题，如果只是把它标记为“已完成”，那这题的价值只发挥了不到三成。它的真正价值在于它是单调栈思维的最小完整示例，后面一堆中等题都能从它身上延伸出来。我这里挑三个最经典的变体，带你看看模板怎么变形。

变体一：下一个更大元素 II，也就是力扣503题。这题把数组变成循环的，意思是最后一个元素的下一个更大元素可以绕到数组开头去找。最常见的处理办法有三种：把数组复制一倍拼成长度2n的新数组，然后跑一遍标准模板；或者遍历2n次，每次用i取模访问原数组；再或者倒着遍历两遍。核心思维就一句话：“循环数组的线性化”——要么拉长数组，要么取模，把环掰成一条线。

变体二：每日温度，也就是力扣739题。这题要求输出的不是“下一个更大元素的值”，而是“下一个更高温度出现在几天后”。因为要算距离，所以栈里必须存下标，不能再存值。出栈结算时，答案不是当前遍历到的值，而是当前下标减去栈顶下标。你看，只要题目从“要什么值”变成“要什么距离”，单调栈模板就要跟着改一个小地方。这也是我说“必须理解模板为什么这么做”的原因，死背模板的人在这里第一次开始出错。

变体三：接雨水，也就是力扣42题。这个题看似和“下一个更大元素”无关，其实也是单调栈的经典应用。它用单调递减栈记录柱子的下标，遇到比栈顶高的柱子时，说明当前区域可以形成凹槽，出栈结算雨水面积。区别在于，前面几题都是“找元素”，接雨水是“找区间、算面积”，需要同时利用出栈元素的高度和左右边界的高度差。

这三道题做完，你对单调栈的理解会有一个质的飞跃。我的建议是做完496后，当天就接着做739，因为两者代码差距最小，最容易体会到“存值和存下标”的区别。然后再花时间啃503和42。

5.2 单调栈的通用套路：识别信号、选方向、套模板

最后总结一套我自己反复用的方法论，专治“什么时候想到用单调栈”这个经典问题。

识别信号。一道题里出现“找数组中每个元素左边或右边第一个比它大或小的元素”，或者出现“下一个更大或更小值”，十有八九是单调栈。类似的信号还有“接雨水”“柱状图中最大矩形”这种需要横向统计区间的问题。

选择方向。找下一个更大元素，用单调递减栈；找下一个更小元素，用单调递增栈。为什么这样配对？因为新元素比栈顶大的时候，才能触发“下一个更大”的结算；反过来，新元素比栈顶小的时候，才能触发“下一个更小”的结算。可以把它理解成：越等待越难满足，遇到更强的才肯放手。

套模板的骨架长这样：

python复制stack = []
ans = [-1] * len(arr)  # 或者用其他初始值
for i, x in enumerate(arr):
    while stack and x > arr[stack[-1]]:  # 破坏单调性时持续出栈
        idx = stack.pop()
        ans[idx] = i  # 或是 x，看题目要什么
    stack.append(i)   # 存下标是通用写法，存值需谨慎

这个骨架里藏着三个可调节的旋钮：比较符号，结算答案时用下标还是用值，栈里存下标还是存值。把这三个旋钮搞懂了，绝大部分单调栈题都是换个皮而已。

我个人在刷单调栈专题时的体会是：每天只刷一道新题，再把之前那道写过的题从头默写一遍，比一天刷十道然后全忘掉有效得多。496这个题尤其适合做“默写练习”，因为它代码短、思路纯粹，练完再回头写739或者42，你会明显感觉到脑子里有一个可迁移的框架在起作用。把一种模型练到肌肉记忆，刷题才不会变成单纯的“看完答案觉得自己会了”。