你好，同学。今天我们要挑战的是单调栈进阶题——循环数组中的下一个更大元素。在 NOI 竞赛中，处理“环形结构”和“线性结构”的转化是必备技巧。

【题目描述】下一个更大元素 II (Next Greater Element II)

题目背景： 在周期性信号处理中，数据往往是循环流动的。我们需要在一个循环数组中，为每一个元素找到其“下一个更大”的观测值。

问题描述： 给定一个循环数组 $nums$（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。 数字 $x$ 的下一个更大元素是按数组遍历顺序，在这个数字之后的第一个比它大的数。这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 $-1$。

输入格式： 第一行包含一个整数 $n$，表示数组长度。 第二行包含 $n$ 个整数，表示数组 $nums$ 的元素。

输出格式： 输出一行 $n$ 个整数，用空格隔开，表示对应的下一个更大元素。

样例输入：

3
1 2 1

样例输出：

2 -1 2

数据范围： 对于 $100\%$ 的数据：$1 \le n \le 10^4$，$-10^9 \le nums_i \le 10^9$。 内存限制：256MB，时间限制：1s。

一、 预备知识点

1. 单调栈 (Monotonic Stack)：解决“寻找下一个更大/更小元素”的标准 $O(n)$ 工具。
2. 环形结构处理：
   • 倍增法：将数组复制一份接在后面（逻辑上变成 $2n$ 长度）。
   • 取模法：通过 i % n 模拟循环遍历。

二、 启发式教学：草稿纸上的推演

1. 突破“环形”的束缚

如果数组是线性的，你会做；现在它是环形的，怎么处理？

• 想法 A：把数组复制一遍，比如 [1, 2, 1] 变成 [1, 2, 1, 1, 2, 1]。
• 观察：在新的长数组里，对前 $n$ 个元素做一遍普通的“下一个更大元素”查询，是不是就涵盖了“绕一圈回来找”的情况？
• 结论：是的。我们只需要遍历 $2n-1$ 次。

2. 草稿纸手绘模拟

假设 $nums = [1, 2, 1]$，$n=3$。我们模拟遍历两次数组（索引 $0 \to 5$）：

1. i=0 (val=1)：栈空，下标 0 入栈。 Stack: {0}
2. i=1 (val=2)：$2 > nums[0]$。
   • 弹出 0，$ans[0] = 2$。
   • 下标 1 入栈。 Stack: {1}
3. i=2 (val=1)：$1 < nums[1]$。
   • 下标 2 入栈。 Stack: {1, 2}
4. i=3 (val=1)：$1$ 不大于 $nums[2]$，也不大于 $nums[1]$。
   • 下标 3%3=0（即0）入栈。 Stack: {1, 2, 0}
5. i=4 (val=2)：$2 > nums[0]$ 且 $2 > nums[2]$。
   • 弹出 0，$ans[0]$ 已有值（可覆盖或跳过，通常更新同一下标没问题）。
   • 弹出 2，$ans[2] = 2$。
   • 1 不弹出（因为 $2$ 不大于 $2$）。
   • 下标 4%3=1 入栈。

注意：结果数组初始化为 $-1$，没被弹出的（如最大值 $2$ 对应的下标 1）自然就是 $-1$。

3. 复杂度与优化思考

• 时间分析：遍历 $2n$ 次，每个下标最多进出栈各一次。$O(2n) = O(n)$。
• 空间分析：栈空间 $O(n)$，结果数组 $O(n)$。
• 优化建议：不需要真的开一个 $2n$ 的数组，用 i % n 访问原数组即可。

三、 算法流程图 (C++14 伪代码思路)

为了确保 Mermaid 渲染正常，我们避开特殊符号，使用描述性文字：

graph TD
    Start(开始: 初始化 ans 数组全为负一) --> LoopInit(遍历 i 从 0 到 2n 减 1)
    LoopInit --> WhileCond{栈不为空 且 当前元素 大于 栈顶下标对应元素}
    WhileCond -- 是 --> PopAction(弹出栈顶下标 topIndex)
    PopAction --> Assign(设置 ans 在 topIndex 处的值为当前元素)
    Assign --> WhileCond
    WhileCond -- 否 --> PushAction(将当前下标 i 取模 n 后压入栈)
    PushAction --> CheckLoop{i 是否达到 2n 减 1}
    CheckLoop -- 否 --> NextIter(i 自增 1)
    NextIter --> LoopInit
    CheckLoop -- 是 --> End(输出 ans 数组)

四、 读题关键词总结 (题眼)

在 NOI 考场上，看到以下描述要立刻警觉：

1. “下一个更大/小” $\rightarrow$ 单调栈。
2. “循环数组/环形” $\rightarrow$ 虚拟倍增 (遍历 $2n$) 或 取模 % n。
3. “搜索不到输出 -1” $\rightarrow$ 初始化数组为 -1。
4. $N$ 在 $10^4$ 到 $10^5$ 级别 $\rightarrow$ 必须是 $O(n)$，不能用嵌套循环。

金牌教练点评： 这题比基础单调栈多了一个“环”的概念。在处理环形问题时，“破环成链”是核心思想。你可以真的开双倍空间，也可以逻辑上遍历两次。对于单调栈，遍历两次足以保证每个元素都能看到它身后的所有元素（包括绕过末尾后的元素）。加油，细节决定成败！