如何求循环数组中的下一个更大元素？

简化版

循环数组的下一个更大元素可以把数组逻辑上遍历两遍，用 i % n 访问真实下标，再用单调递减栈维护还没找到更大值的位置。只在第一遍入栈，第二遍负责让尾部元素有机会看到头部元素，整体 O(n)。

详细版

普通下一个更大元素只看右侧；循环数组还要允许末尾继续看数组开头。例如 [1,2,1] 中最后一个 1 的下一个更大元素是 2。做法是遍历 2n 次，当前下标为 idx = i % n，当 nums[idx] 大于栈顶对应值时弹栈并记录答案。

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.peek()]) {
            ans[stack.pop()] = nums[idx];
        }
        if (i < n) stack.push(idx);
    }
    return ans;
}

关键点是第二遍不能重复入栈，否则同一个位置可能被重复处理；第二遍只提供“环形右侧”的候选值。

完整版教学

一、循环数组比普通数组多了什么

普通数组中，位置 i 的右侧是 i+1..n-1。循环数组中，右侧还可以继续绕到 0..i-1。所以对 [1,2,1] 来说，最后一个 1 右侧逻辑序列是 [1之后绕回的1,2]，答案是 2。

真实数组:  [1, 2, 1]
逻辑展开:  [1, 2, 1, 1, 2, 1]
下标映射:   0  1  2  0  1  2

逻辑展开不需要真的复制数组，只要用 i % n 映射即可。

二、为什么仍然用单调递减栈

问题仍然是“找右侧第一个更大值”，只是右侧的范围从线性变成环形。单调递减栈保存还没找到更大值的下标，当当前值更大时，栈顶下标的答案就是当前值。

例如 [2,1,2,4,3]，扫描到 4 时，它会解决前面的 2、1、2；扫描第二遍到 4 之前，末尾的 3 会看到开头的 2 但不弹，最终仍无更大值，答案是 -1。

三、为什么遍历两遍就够

每个位置最多只需要看自己后面的 n-1 个元素。把数组逻辑上拼接一份后，任意位置 i 的环形右侧都包含在 i+1..i+n-1 里。因此遍历 2n 次已经覆盖所有可能候选，不需要无限循环。

位置 3 在长度 5 数组中:
可见顺序 = 4,0,1,2
逻辑展开里 = 3 后面的 4 个位置

超过两遍只会重复看已经看过的候选，不会产生新答案。

四、为什么第二遍不再入栈

第一遍入栈的是每个真实下标。第二遍的作用只是提供“绕回来”的当前值，帮助第一遍遗留的下标出栈。如果第二遍继续入栈，同一个下标会出现两份副本，答案可能被重复设置，也会让理解变乱。

阶段	是否入栈	作用
第一遍 `0..n-1`	是	注册每个位置等待答案
第二遍 `n..2n-1`	否	提供环形候选值

答案数组初始化为 -1，第二遍结束还没被弹出的下标，就是真的没有更大元素。

五、代码实现与复杂度

核心循环只需要三个判断：取模得到真实下标、while 弹出能被当前值解决的候选、第一遍才入栈。

for (int i = 0; i < 2 * n; i++) {
    int idx = i % n;
    while (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
        ans[stack.pop()] = nums[idx];
    }
    if (i < n) {
        stack.push(idx);
    }
}

复杂度不是 O(2n²)，因为每个真实下标只入栈一次、出栈一次。遍历次数是 2n，弹栈总次数最多 n，所以时间 O(n)，空间 O(n)。

六、常见误区与追问

记忆钩子：循环数组不是“无限向右找”，而是“最多多看一圈”。第一圈入栈，第二圈结账。

误区：需要真的复制一份数组。 不需要，i % n 就能模拟逻辑展开，避免额外 O(n) 拷贝。
误区：第二遍也要入栈。 第二遍只提供候选值，重复入栈会让同一下标被处理多次。
误区：用 >= 弹栈。 “更大元素”要求严格大于，相等不能作为答案。
追问：为什么不是遍历 2n - 1？ 2n 写法简单且覆盖完整；实际最后一次不会产生新入栈，复杂度不变。
追问：数组全递减怎么办？ 例如 [5,4,3]，4 和 3 能在第二遍看到 5，5 没有更大值。
追问：和每日温度区别是什么？ 每日温度返回距离，循环数组题通常返回值；栈模型相同，答案写法不同。

七、加强记忆

循环数组的技巧是“数组不复制，视野复制”：用 2n 次扫描模拟看两圈，用 i % n 回到真实下标。单调递减栈仍保存未找到更大值的位置，第一遍入栈、第二遍只解题，最后没弹出的保持 -1。把这三点连起来，就能稳定写出代码。

简化版

详细版