LeetCode 503. 下一个更大元素 II

约 5 分钟
文章信息 15 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 微软 阿里巴巴 快手 腾讯 滴滴 华为 旷视 虾皮 作业帮
标签
数组 栈 单调栈 下一个更大元素问题 单调栈经典题
目录

题目描述

✅ 503. 下一个更大元素 II

image-20230818153430400

题意分析

给的是一个「首尾相接」的数组，要为每个位置回答同一个问题：沿着向右的方向走，遇到的第一个严格大于它的值是多少；走到末尾要绕回开头继续找，最多绕一整圈回到自己，仍然找不到就填 -1。
「严格大于」是硬约束，和自己相等的值不算答案，所以元素全部相同的数组，答案全是 -1。
约束信号有两个：一是数组长度上限一万，$O(n^2)$ 能勉强通过却不是面试想听的答案；二是题目特意把「环形」写进条件，说明考点不在朴素查找，而在怎么处理回绕，并且回绕不能靠真的复制出一个两倍长的新数组。
边界要想清楚：长度为 1 时唯一的答案只能是 -1；严格递减的数组里，最大值的答案是 -1，其余每个元素都必须绕回开头才能拿到答案；无论绕多少圈，输出数组的长度始终是原数组长度 n，环形只影响查找范围，不影响结果规模。

解法：循环遍历 + 单调栈

核心思路

题目要找每个位置向右遇到的第一个严格更大值，而且查找可以绕回数组开头。逐个位置向后扫描会重复经过大量区间，最坏是 $O(n^2)$；「右侧第一个更大元素」应使用单调栈消除重复扫描。

栈中保存尚未找到答案的下标，从栈底到栈顶对应的数值单调不增。扫描到当前值 nums[idx] 时，只要它严格大于栈顶值，就弹出栈顶并把当前值写入其答案；一个较大值可能连续结算多个位置，所以必须使用 while。

不变量是：栈内每个下标都没有在已经扫描过的区间中遇到更大值。若下标 j 在当前位置被弹出，那么 j 到当前位置之间没有值能弹出它，而当前值第一次满足严格更大，因此它就是 j 的正确答案。

环形数组无需真的复制。扫描虚拟区间 $[0,2n)$，用 idx = i % n 映射回原数组；第一轮把每个下标入栈一次，第二轮只负责补齐跨越数组尾部的答案。结束后仍在栈中的位置绕一圈也找不到更大值，保留初始值 -1。

解题步骤

  • 创建长度为 $n$ 的答案数组并填充 -1，栈中存放原数组下标。
  • 遍历 i = 0 到 2n - 1，令 idx = i % n。
  • 当栈非空且 nums[idx] > nums[stack.top] 时持续弹栈，并令被弹下标的答案等于 nums[idx]。
  • 仅在 i < n 时将 idx 入栈，保证每个下标最多入栈一次。
  • 返回答案数组；无需单独处理栈中剩余下标。

以 [1, 2, 1] 为例：第一轮中 2 结算下标 0，栈中留下值为 2、1 的下标；第二轮绕到 2 时结算最后一个 1，结果为 [2, -1, 2]。

代码实现

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

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)$。虽然扫描两轮且含有内层循环，但每个下标只入栈一次、最多出栈一次，所有弹栈次数合计不超过 $n$。
  • 空间复杂度：$O(n)$。单调栈最坏保存全部下标；答案数组不计入额外空间。

关键点总结

  • 栈存下标而不是数值，才能在结算时定位答案位置。
  • 栈维护的是「尚未找到答案」的候选，下标对应值保持单调不增。
  • 用两轮下标取模模拟环形；第二轮只结算、不重复入栈。
  • 正确性来自「弹栈时当前值是扫描顺序中第一个严格更大值」，线性复杂度来自每个下标至多进出栈一次。

易错点总结

  • 比较条件写成 >=：相等元素会被误认为更大，例如 [2, 2] 应返回 [-1, -1]。
  • 只扫描一轮：[1, 2, 1] 的最后一个 1 无法绕回开头找到 2。
  • 第二轮继续入栈：同一下标被重复处理，破坏一次进出栈的约束。
  • 用 if 代替 while：当前值只能结算一个位置，连续更小的栈元素会被漏掉。
  • 未预填 -1：没有更大值的位置会保留语言默认的 0。

相似题目

题目 难度 考察点
496. 下一个更大元素 I 简单 线性数组不绕圈，多一层「子集元素查母数组」的哈希映射
739. 每日温度 中等 要的是下标之差而不是数值，弹栈时输出 i - 栈顶
1019. 链表中的下一个更大节点 中等 载体是链表，需先定长度或边遍历边扩展答案容器
LCR 038. 每日温度 中等 与 739 同题不同编号，可用来检验模板是否真的记牢