你好！我是你的OI竞赛教练。我们继续深入数据结构专题。

今天这节课，我们要攻克的是单调栈的进阶应用——环形数组（Circular Array）。

很多同学在做 LeetCode 503 或者类似 OI 题目时，面对“首尾相连”的数组往往会手忙脚乱，或者写出 $O(N^2)$ 的暴力解法导致 TLE。这节课我们彻底把“化圆为直”的技巧讲透。

---

OI 专题：环形数组与单调栈优化

Topic: Cycle Array & Monotonic Stack

1. 预备知识点 (Prerequisites)

在切入正题前，请自查是否掌握以下基础：

1. 单调栈（Monotonic Stack）：
   • 定义：栈内元素保持单调递增或递减。
   • 用途：$O(N)$ 时间内找到数组中某个元素右侧（或左侧）第一个比它大（或小）的元素。
   • 口诀：求“下一个更大”，用单调递减栈；求“下一个更小”，用单调递增栈。
2. 取模运算（Modulo Arithmetic）：
   • 性质：i % n 的结果永远在 [0, n-1] 之间。
   • 用途：利用取模实现下标的循环移动。

---

2. 读题关键词 (Keywords Extraction)

在读题时，一旦捕捉到以下关键词，你的“雷达”应当立即响应该技巧：

• “循环数组” (Circular Array / Cyclic Array)
• “首尾相连” (End connected to start)
• “下一个...” (Next Greater/Smaller Element)
• “环形”

教练批注：

只要题目涉及“环”，解题的核心思想永远只有一句话：不要真的去建一个环形链表，而是通过“翻倍”或“取模”在逻辑上模拟环。

---

3. 启发式推演：如何在草稿纸上思考 (Heuristic Reasoning)

假设题目是：给定一个环形数组，求每个元素的下一个更大元素。如果不存输出 -1。 数组：[2, 1, 2, 4, 3]

步骤一：遇到思维墙 (The Block)

学生：教练，如果是普通数组，我倒着遍历一遍，维护一个递减栈就行了。 比如 [..., 4, 3]，处理 3 时，栈里有 4，答案就是 4。 但是现在是环形的，末尾的 3 的下一个更大元素其实是开头的 4（下标 3）。可是我倒着遍历时，开头的元素还没进栈呢！

步骤二：朴素的物理模拟 (Physical Simulation)

教练：别急。如果我们要让末尾的 3 能“看到”开头的 2, 1...，最暴力的物理手段是什么？ 学生：把数组复制一份拼在后面？

请在草稿纸上画出这个图：

原始索引:  0  1  2  3  4
原始数值: [2, 1, 2, 4, 3]

物理拼接后:
新索引:    0  1  2  3  4  5  6  7  8  9
数值:     [2, 1, 2, 4, 3, 2, 1, 2, 4, 3]
                         ^
                         |___ 此时末尾的3往后看，就能看到5号位的2(即原本的0号位)了

教练：对！变成长度 2N 的线性数组后，这不就是一道最基础的单调栈题目了吗？

步骤三：优美的数学模拟 (Virtual Simulation)

教练：在比赛中，如果 $N=10^5$，你真的要 vector 扩容一倍吗？这会浪费空间和拷贝时间。 观察上面的草稿，新索引 5 对应原数组索引 0，6 对应 1... 请归纳公式：对于任意新索引 i (从 $0$ 到 $2N-1$)，它对应的真实数据索引是多少？

学生：real_index = i % N

教练总结： 我们不需要真的申请 2N 的空间。我们只需要在循环次数上假装是 2N，但在访问数据时通过取模回到原数组。

---

4. 核心解题流程 (The Algorithm)

1. 定义栈：使用 std::stack，存储元素的值（或者下标，视题目要求而定，存值较简单）。
2. 倒序遍历：为了使用单调栈求“右侧第一个更大”，通常从右向左遍历。
   • 循环变量 i 从 2 * n - 1 开始，递减到 0。
3. 映射下标：计算 curr = nums[i % n]。
4. 单调栈操作：
   • Pop：若栈顶元素 $\le$ curr，说明栈顶元素太矮了，被 curr 挡住了，对于 curr 左边的人来说，curr 是更好的选择（或者一样差），所以弹出栈顶。重复此步直到栈空或栈顶 $>$ curr。
   • Record：此时栈顶就是 curr 的下一个更大元素。
   • Push：将 curr 入栈。

---

5. OI 风格代码实现 (C++14 Standard)

/**
 * 知识点：单调栈 + 环形数组处理技巧
 * 风格：OI 竞赛标准 (Fast I/O, Concise Logic)
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
// 全局数组，防止爆栈，OI习惯
int a[MAXN]; 
int ans[MAXN];

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        // 单调栈，这里我们存数值
        // 如果题目要求输出下标，则栈里应该存下标
        stack<int> s;

        // 2. 核心逻辑：假装数组长度翻倍
        // 遍历范围：[2n-1, 0]
        for (int i = 2 * n - 1; i >= 0; --i) {
            // 关键点：利用取模模拟环形索引
            int realIndex = i % n; 
            
            // 3. 维护单调递减栈 (栈底大 -> 栈顶小)
            // 我们要找的是“更大”的，所以比当前矮的元素统统弹出
            while (!s.empty() && s.top() <= a[realIndex]) {
                s.pop();
            }

            // 4. 记录答案
            // 只有当 i < n 时才需要记录到结果数组中
            // i >= n 的部分只是为了给前半部分填充栈数据（充当“幻影”）
            if (i < n) {
                if (!s.empty()) {
                    ans[realIndex] = s.top();
                } else {
                    ans[realIndex] = -1;
                }
            }

            // 5. 当前元素入栈
            s.push(a[realIndex]);
        }

        // 输出结果
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

---

6. 课后实战演练 (Practice Problem)

这里有一道完全符合上述知识点的模拟题，请在 15 分钟内 AC。

题目：圆桌骑士的挑战

【题目描述】 亚瑟王的 $N$ 名圆桌骑士围坐在一张圆桌旁。每位骑士都有一个战斗力值 $A_i$。骑士们顺时针编号为 $0$ 到 $N-1$。 为了备战，每位骑士都想知道，沿着顺时针方向，第一个战斗力比自己高的骑士的战斗力是多少。 如果转了一圈也没找到比自己强的骑士，则输出 -1。

【输入格式】 第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示骑士的数量。 第二行包含 $N$ 个整数 $A_0, A_1, \dots, A_{N-1}$ ($0 \le A_i \le 10^9$)，表示每位骑士的战斗力。

【输出格式】 输出一行，包含 $N$ 个整数。第 $i$ 个整数表示第 $i$ 位骑士顺时针方向遇到的第一个比他强的骑士的战斗力。如果不存，输出 -1。整数之间用空格分隔。

【样例输入 1】

3
1 2 1

【样例输出 1】

2 -1 2

【样例输入 2】

5
2 1 2 4 3

【样例输出 2】

4 2 4 -1 4

【数据范围】 对于 $30\%$ 的数据，$N \le 100$。 对于 $100\%$ 的数据，$N \le 10^5$。

---

教练的最后提示 (Final Hint)

这道题就是典型的Next Greater Element II 模板题。

1. 注意数据范围 $N=10^5$，暴力 $O(N^2)$ 会超时，必须用 $O(N)$ 的单调栈。
2. 注意 "顺时针" 和 "圆桌"，暗示 i % n 的技巧。
3. 不要忘记 ios::sync_with_stdio(false)。

开始动手写代码吧！