LeetCode 503. 下一个更大元素 II

约 5 分钟
文章信息 15 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 阿里 华为 微软 快手 滴滴 虾皮 旷视 作业帮
标签
数组 栈 单调栈

题目描述

✅ 503. 下一个更大元素 II

image-20260928203620397

题意分析

对数组中的每个位置，沿着下标增大的方向寻找第一个严格大于它的元素，并返回这个元素的值。到达数组末尾后可以回到开头继续找；转完一圈仍没有找到，就在该位置返回 -1。

这里的“下一个”按沿途遇到的先后顺序判断，不是所有更大值中的最小值；相等值也不满足要求。不同位置即使数值相同，也要分别确定答案，返回结果与原数组下标一一对应。

解法：循环遍历 + 单调栈

核心思路

[!blue]

如果对每个位置分别向后寻找，最坏会反复扫描整个数组。换一个方向考虑：读取当前数值时，可以同时为此前还没有答案、且比它小的位置确定答案。用栈保存这些待解决位置的下标，方便直接写回对应的答案。

栈中下标对应的数值从底到顶保持单调不增。遇到当前值时，只要它严格大于栈顶，就弹出栈顶并记录答案；持续处理，直到栈空或栈顶不比当前值小。如果连栈顶都不小于当前值，更深处的数值只会更大，也就无需继续检查。

被弹出的位置此前一直留在栈中，说明从它出现到现在还没有遇到严格更大的值。扫描按右侧方向依次前进，因此此时遇到的当前值就是第一个更大值，而非随意找到的一个更大值。

为了覆盖跨越数组末尾的搜索，将遍历下标扩展为 [0, 2n)，实际访问 nums[i % n]，相当于把原数组连续读两遍。第一遍把每个原下标入栈一次；第二遍只为旧下标补答案，不再添加待处理项。这样每个位置之后的一整圈都被覆盖，仍留在栈里的位置没有更大元素，保留初始答案 -1。

解题步骤

  1. 创建长度为 n 的答案数组并全部填为 -1，准备保存下标的空栈。
  2. 依次遍历 i = 0..2n-1，令 idx = i % n，取出本次访问的数值。
  3. 当栈非空且当前值严格大于栈顶对应值时，弹出该下标，并把它的答案设为当前值。
  4. 弹栈结束后，仅当 i < n 时将 idx 入栈；第二遍只处理仍未解决的位置。
  5. 两遍扫描完成后返回答案，栈中剩余位置无需再赋值。

代码实现

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;

            while (!stack.isEmpty() && nums[idx] > nums[stack.peekLast()]) {
                ans[stack.pollLast()] = nums[idx];
            }

            // 第一圈登记待求下标，第二圈只补齐旧候选的后继，避免重复记录。
            if (i < n) {
                stack.offerLast(idx);
            }
        }

        return ans;
    }
}

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    stack := make([]int, 0, n)

    for i := 0; i < 2*n; i++ {
        idx := i % n
        for len(stack) > 0 && nums[idx] > nums[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            ans[top] = nums[idx]
        }
        // 第一圈登记待求下标，第二圈只补齐旧候选的后继，避免重复记录。
        if i < n {
            stack = append(stack, idx)
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(n)。外层访问 2n 个位置；每个原下标只入栈一次、最多出栈一次，内层全部弹栈次数之和不超过 n。
  • 空间复杂度：O(n)。单调栈最坏保存全部下标；返回的答案数组不计入额外空间。

关键点总结

[!green]

  • 单调栈记录尚无答案的位置，当前更大值可以同时解决连续多个栈顶。
  • “第一个”由扫描顺序和未解决状态共同保证，不需要额外比较候选答案。
  • 两遍扫描解决环形边界，但只在第一遍入栈，保证每个答案只结算一次。

易错点总结

[!yellow]

  • 比较时使用 >=：题目要严格更大，相等数不能成为答案，必须继续等待。
  • 栈中只保存数值：存在重复元素时无法知道应该填回哪个结果位置，需要保存下标。
  • 用 if 代替 while 弹栈：一个当前值可能为多个位置提供答案，只弹出一个会漏掉其余位置。
  • 只遍历原数组一次：靠后的位置无法到开头寻找更大值，需要额外一圈补齐。
  • 第二遍继续重复入栈：会重复登记已经存在或处理完的原下标，与“一次入栈、一次结算”的实现约定不符。
  • 不预填 -1：没有更大值的位置会错误保留数组默认值零。

相似题目

题目 难度 关联与区别
496. 下一个更大元素 I 简单 把线性下一更大元素扩展为环形，通过额外扫描补足跨首尾的候选。
739. 每日温度 中等 单调栈维护尚未找到更大值的位置，本题返回值且存在环，原题返回线性距离。
1019. 链表中的下一个更大节点 中等 用单调栈确定最近的更大元素；本题循环扫描以覆盖跨边界候选，该题先把链表值转为顺序序列处理。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18328478
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！