下一个更大元素 II 图解题解

这道题到底在问什么

nums

[1, 2, 3, 4, 3]

输出

[2, 3, 4, -1, 4]

环形

末尾的 3 绕回开头，撞上第 2 个 4

最优解：一步一步想明白

1. 3环形 = 数组首尾相连成一个圈。走到末尾不停，绕回开头继续找，直到回到自己为止。
2. 4每个元素都可能向后扫将近 n 个，n 个元素就是 n×n 次比较，数据一大就慢得不行。
3. 5把「还没找到答案」的下标攒起来。一旦来了个大数，它可能正是这些等待者要找的答案，一次性结清。
4. 6下面动画里，紫色高亮的格子就是栈里「还在排队等更大数」的下标；蓝色是已结清、cur 指针是当前扫到的位置。盯住这三样怎么变。
5. 7走两圈就等于「每个数都向后看了一整圈」。第二圈不再往栈里压新下标，只用它们去结清第一圈还没解决的等待者。
6. 8栈 [] · 答案全 -1答案先全填 -1（默认没人更大）。栈空着，准备装「还没找到更大元素的下标」。下方 RESULT 行就是实时答案，紫格会代表栈内容。
7. 9栈空 → 下标 0 入栈i=0，值是 1。栈是空的，没人在等它，直接把下标 0 压进栈（变紫）——它开始排队等自己的「更大元素」。
8. 10cur=2 vs 栈顶下标0 值1i 走到 1，值是 2。先和栈顶（紫格下标 0）比：栈顶值是 1，2 比 1 大！这意味着下标 0 苦等的更大数到了。
9. 11答案[0]=2，下标0 出栈弹出下标 0，记下 答案[0]=2（RESULT 行第一格变 2）。它变成蓝色——已结清，离开栈。
10. 12下标 1 入栈排队栈空了，轮到下标 1 自己排队——把它压栈（紫格移到下标 1），等它将来的更大数。
11. 13cur=3 vs 栈顶下标1 值2i 走到 2，值是 3。和栈顶（下标 1，值 2）比：3 比 2 大，又能结清一个。
12. 14答案[1]=3，下标1 出栈弹出下标 1，记 答案[1]=3。下标 0、1 都已结清（蓝色）。栈又空了。
13. 15下标 2 入栈排队把当前下标 2 压栈（紫格到下标 2），它开始排队。
14. 16cur=4 vs 栈顶下标2 值3i 走到 3，值是 4。和栈顶（下标 2，值 3）比：4 更大。每个新数进来，会把栈里所有比它小的等待者一口气结清。
15. 17答案[2]=4，下标2 出栈弹出下标 2，记 答案[2]=4。前三个都结清了（蓝色）。
16. 18下标 3 入栈排队把下标 3（值 4，全场最大）压栈排队。它能不能等到更大的？往下看。
17. 19cur=3 vs 栈顶下标3 值4i 走到 4，值是 3。和栈顶（下标 3，值 4）比：3 没有 4 大，结不了 4 的账，不弹。
18. 20下标 4 也入栈 → 栈 [3,4]下标 4 自己也还没找到更大的，把它也压栈。现在紫格 = 下标 3 和 4，对应值 [4,3]，从底到顶递减。第一圈走完，这两个还没结清。
19. 21第二圈的作用：让末尾这些没找到答案的数，能去「看」开头的元素。第二圈只结账、不再压新下标，否则会重复处理。
20. 221 < 栈顶值3 → 不弹i=5，i%n=0，cur 绕回开头看 nums[0]=1。栈顶下标 4 的值是 3，1 比 3 小，结不了账。第二圈不压栈，i 继续走。
21. 232 < 栈顶值3 → 不弹i=6，cur 移到下标 1，值 2。栈顶下标 4 的值还是 3，2 仍然不够大，不弹。继续。
22. 243 = 栈顶值3 → 不弹(要严格大)i=7，cur 移到下标 2，值 3。栈顶下标 4 的值也是 3，一样大不算「更大」，要严格大于才弹——这是个容易写错的细节，所以不动。
23. 25cur=4 vs 栈顶下标4 值3i=8，cur 移到下标 3，值 4。和栈顶（下标 4，值 3）比：4 比 3 大！终于来了能结清下标 4 的数。
24. 26答案[4]=4 ← 绕圈撞上的 4弹出下标 4，记 答案[4]=4——这正是「最后那个 3 绕一圈撞上下标 2 的 4」的过程！下标 4 变蓝结清，栈只剩下标 3。
25. 273 < 栈顶值4 → 不弹i=9，最后一步，cur 到下标 4，值 3。栈顶下标 3 的值是 4，3 比 4 小，结不了账。2n 步走完了。
26. 28下标3 一直没人比它大 → -1走完两圈，栈里还剩下标 3（值 4，全场最大）。它从没被弹出，说明绕一整圈都没人比它大，保持默认 -1。最终答案 [2,3,4,-1,4]。
27. 29关键账：每个下标最多入栈一次、出栈一次，2n 次循环里总操作数被钉死在常数倍 n，所以是 O(n)。
28. 32新来一个数，就把候车室里所有「比它小」的等待者一次结清。凡是「找下一个更大/更小」的题，第一反应就该想到单调栈。
29. 33每日温度(LC739)、下一个更大元素 I(LC496) 骨架完全一样，区别只在「存什么、比较方向、要不要绕圈」。
30. 35nums=[3,3] 若用 ≤ 会误判nums=[3,3]，正确答案该是 [-1,-1]（没人严格更大）。但若比较写成 ≤，遇到第二个 3 会误判它「更大」，把答案[0] 错填成 3。所以必须严格 <。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        res = [-1] * n             # 默认找不到 → -1
        stack = []                 # 存还没找到更大元素的下标
        for i in range(2 * n):     # 遍历两圈处理环形
            cur = nums[i % n]      # 取真实位置的值
            while stack and nums[stack[-1]] < cur:  # 严格更大才结清
                res[stack.pop()] = cur
            if i < n:              # 只在第一圈压入下标
                stack.append(i)
        return res

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);          // 默认 -1
        stack<int> st;                   // 存下标
        for (int i = 0; i < 2 * n; i++) {   // 走两圈
            int cur = nums[i % n];
            while (!st.empty() && nums[st.top()] < cur) {  // 严格更大
                res[st.top()] = cur; st.pop();
            }
            if (i < n) st.push(i);       // 只第一圈压栈
        }
        return res;
    }
};

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);            // 默认 -1
        Deque<Integer> stack = new ArrayDeque<>();  // 存下标
        for (int i = 0; i < 2 * n; i++) {   // 走两圈
            int cur = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < cur) {  // 严格更大
                res[stack.pop()] = cur;
            }
            if (i < n) stack.push(i);    // 只第一圈压栈
        }
        return res;
    }
}

复杂度

面试官可能追问