054 · Next Greater Element I

algorithm

Published

July 7, 2026

My First Thoughts

嗯，这道题里 nums1 是 nums2 的子集，对吧。

答案要按 nums1 的顺序返回，但是每个数字的“下一个更大元素”要去 nums2 里面找。

最直接的想法是遍历 nums1：

for num in nums1:

然后对每个 num，先在 nums2 里找到它的位置：

for i in range(0, len(nums2)):
    if num == nums2[i]:

找到以后，再从 i + 1 开始往右走，看看有没有第一个比它大的数：

for j in range(i + 1, len(nums2)):
    if nums2[j] > num:

这样逻辑上是可以的。

如果这个 num 本来就在 nums2 的最后一个位置，那右边已经没有数字了，答案肯定是 -1。

如果右边一路都没有找到更大的数字，答案也是 -1。

整理一下，暴力写法大概是：

def nextGreaterElement(nums1, nums2):
    result = []

    for num in nums1:
        i = 0

        while nums2[i] != num:
            i += 1

        j = i + 1

        while j < len(nums2) and nums2[j] < num:
            j += 1

        if j == len(nums2):
            result.append(-1)
        else:
            result.append(nums2[j])

    return result

这个基本可以解出来。

但是这个方法显然负担比较大。每次都要先在 nums2 里面找位置，再从那个位置继续往右找。nums2 是固定的，可是我们对 nums1 里的每个数字都重新扫了一遍。

然后会想到：能不能先记住 nums2 里每个数字对应的答案？

也就是用一个字典：

right = {}

让每个 num 作为 key，value 就是它右边第一个更大的数字。

如果能提前得到这样的关系：

right[1] = 3
right[3] = 4
right[4] = -1
right[2] = -1

那么最后只要按 nums1 的顺序取：

return [right[num] for num in nums1]

问题就简单了。

真正卡住的是：这个 right 字典怎么高效建立？

一开始可能会想用 max 和 next 这样的变量配合字典来做。

比如字典里先把一些数字的答案记成 -1，然后继续往右遍历。等遇到一个新的当前值时，如果它比前面某些数字更大，就尝试用当前值去替换前面的 -1。

这里的 max 是遍历过程中见过的最大状态。它可以帮助判断当前值是不是刷新了某种已知范围。next 则可以用来判断某个候选答案是不是比当前数字大。

这个方向其实已经很接近正解了：你已经想到要用字典保存：

right[num] = num 的下一个更大元素

也已经想到，这个答案不是一开始就固定的，可能会随着继续遍历 nums2 被当前值补上。

真正难整理的是：前面可能不止一个数字还在等答案。

比如：

nums2 = [1, 3, 4, 2]

看到 3 时，1 可以被 3 解决。

看到 4 时，3 可以被 4 解决。

但换成：

nums2 = [1, 2, 3]

看到 3 时，它不只可能影响最近的 2，还可能继续影响更前面的 1。

所以问题可能更加复杂

Why That Is Not Enough

暴力解法本身是正确的，问题主要是重复工作太多。

对每个 nums1 里的数字，都重新去 nums2 里找位置，再重新往右扫描。最坏情况下会接近：

len(nums1) * len(nums2)

而 nums2 其实只需要分析一次。

另外，max + next + 字典回填 的方向已经抓到了“提前建立映射”这件事，但还缺一个清晰的候选集合。因为这题同时关心两个条件：

必须在当前数字右边
必须是右边第一个比它大的数字

也就是说，当前值可能要回填前面的多个数字，而不是只更新一个 max 或一个 next。

更合适的状态不是只记录一个最大值，而是记录：

现在有哪些数字还没有找到自己的右边第一个更大元素？

这些数字可以放在一个栈里。

Final Idea

先遍历一次 nums2，建立一个字典 right：

right[num] = num 右边第一个更大的数字

如果不存在，就记为 -1。

关键是用一个栈 stack 保存：

已经见过，但是还没有找到右边第一个更大元素的数字。

从左到右遍历 nums2。

当看到一个新数字 num 时，它可能就是栈里一些数字一直在等的“右边第一个更大元素”。

如果：

num > stack[-1]

说明当前 num 比栈顶数字大。因为我们是从左到右第一次遇到这个更大的数，所以它就是栈顶数字的答案。

于是可以：

smaller = stack.pop()
right[smaller] = num

但这件事可能不只发生一次。

比如：

nums2 = [1, 2, 3]

看到 3 的时候，它不只比 2 大，也比更早还没解决的 1 大。

所以这里不是 if，而是 while：

while stack and num > stack[-1]:
    smaller = stack.pop()
    right[smaller] = num

把所有能被当前 num 解决的数字都解决掉。

如果当前 num 不能解决栈顶，或者栈已经空了，就把当前 num 自己放进栈里，等待以后右边更大的数字：

stack.append(num)

遍历结束后，栈里还剩下的数字，说明它们右边没有更大的元素，答案都是 -1。

最后按 nums1 的顺序查字典即可。

Why It Works

栈里保存的是“还没有找到答案的数字”。

从左到右遍历 nums2 时，当前数字 num 一定在栈里所有数字的右边。

如果 num 比栈顶数字大，那么对栈顶数字来说，num 就是它右边第一个更大的元素。

为什么是“第一个”？

因为栈顶数字被放入栈以后，中间遇到过的数字都没有把它弹出来。也就是说，中间那些数字都不比它大。现在第一次遇到一个更大的 num，所以这个 num 就是它要找的第一个更大元素。

弹出栈顶以后，还要继续比较新的栈顶。

这是因为同一个 num 可能同时解决多个更小的数字。

比如：

nums2 = [1, 3, 4, 2]

过程是：

看到 1：stack = [1]
看到 3：3 > 1，所以 right[1] = 3，stack = []，再把 3 放入 stack
看到 4：4 > 3，所以 right[3] = 4，stack = []，再把 4 放入 stack
看到 2：2 不能解决 4，把 2 放入 stack

最后栈里还有：

[4, 2]

说明 4 和 2 右边都没有更大的数字，所以它们的答案都是 -1。

得到：

right = {
    1: 3,
    3: 4,
    4: -1,
    2: -1,
}

然后 nums1 = [4, 1, 2]，所以答案是：

[-1, 3, -1]

Code

def nextGreaterElement(nums1, nums2):
    right = {}
    stack = []

    for num in nums2:
        while stack and num > stack[-1]:
            smaller = stack.pop()
            right[smaller] = num

        stack.append(num)

    while stack:
        right[stack.pop()] = -1

    result = []

    for num in nums1:
        result.append(right[num])

    return result

也可以把最后几行写得更短：

return [right[num] for num in nums1]

Complexity

Time	\(O(n + m)\) - `n` 是 `nums2` 的长度，`m` 是 `nums1` 的长度；`nums2` 中每个数字最多入栈一次、出栈一次，最后再遍历一次 `nums1`
Space	\(O(n)\) - `right` 字典和 `stack` 最多保存 `nums2` 中的所有数字

Takeaway

当你已经想到“用字典记录每个元素的答案”，但不知道怎么高效建立这个字典时，可以反过来问：哪些元素还没等到答案？如果新元素能解决最近等待的元素，就用栈和 while 一直弹出，把这一批答案一次性填好。

← Quiz