在 NOI 竞赛中，构造数据不仅要考虑数据规模，还要考虑数据的分布特性，以确保能过滤掉各种错误的贪心或暴力算法。

针对“下一个更大元素 II”，数据生成的难点在于处理环形搜索和大范围整数。下面这个生成器会生成 10 个测试点，覆盖从基础样例到极限性能测试的各种情况。

【数据生成器 C++ 代码】

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>

using namespace std;

// --- 标准答案算法 (O(n) 单调栈) ---
// 采用迭代写法，逻辑上模拟遍历 2n 次
void solve(int n, const vector<int>& nums, vector<int>& ans) {
    ans.assign(n, -1);
    static int stk[200005]; // 栈内存：存储下标
    int top = 0;
    
    // 遍历两遍数组，确保环形逻辑覆盖
    for (int i = 0; i < 2 * n; ++i) {
        int val = nums[i % n];
        while (top > 0 && val > nums[stk[top]]) {
            int prev_idx = stk[top--];
            ans[prev_idx] = val;
        }
        // 只在第一轮时入栈，减少冗余操作
        if (i < n) {
            stk[++top] = i;
        }
    }
}

// --- 文件读写辅助 ---
void writeInput(int id, int n, const vector<int>& nums) {
    ofstream fout(to_string(id) + ".in");
    fout << n << "\n";
    for (int i = 0; i < n; ++i) {
        fout << nums[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
}

void writeOutput(int id, int n, const vector<int>& ans) {
    ofstream fout(to_string(id) + ".out");
    for (int i = 0; i < n; ++i) {
        fout << ans[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
}

int main() {
    mt19937_64 rng(20251223); // 使用 64 位随机种子
    auto getRand = [&](long long l, long long r) {
        return (int)uniform_int_distribution<long long>(l, r)(rng);
    };

    const int MAX_VAL = 1000000000;

    for (int t = 1; t <= 10; ++t) {
        int n;
        vector<int> nums;

        if (t == 1) { // 样例
            n = 3; nums = {1, 2, 1};
        } else if (t == 2) { // 最小边界
            n = 1; nums = {getRand(-MAX_VAL, MAX_VAL)};
        } else if (t == 3) { // 严格递增 (除了最大值，其余结果为 nums[i+1])
            n = 1000;
            for (int i = 0; i < n; i++) nums.push_back(i);
        } else if (t == 4) { // 严格递减 (环形寻找，结果多为 nums[0])
            n = 1000;
            for (int i = 0; i < n; i++) nums.push_back(n - i);
        } else if (t == 5) { // 全部相等 (结果全部为 -1)
            n = 2000;
            int v = getRand(-MAX_VAL, MAX_VAL);
            nums.assign(n, v);
        } else if (t == 6) { // 含有大量负数的大规模随机数据
            n = 5000;
            for (int i = 0; i < n; i++) nums.push_back(getRand(-MAX_VAL, 0));
        } else if (t == 7) { // 锯齿形数据 (Up-Down-Up)
            n = 8000;
            for (int i = 0; i < n; i++) nums.push_back(i % 2 == 0 ? 100 : 50);
        } else if (t == 8) { // V 型数据 (先降后升)
            n = 10000;
            for (int i = n/2; i >= 1; i--) nums.push_back(i);
            for (int i = 1; i <= n/2; i++) nums.push_back(i);
        } else if (t == 9) { // 只有一个全局最大值在中间
            n = 10000;
            for (int i = 0; i < n; i++) nums.push_back(getRand(1, 1000));
            nums[n/2] = MAX_VAL;
        } else { // 满负荷随机测试 (N = 10000)
            n = 10000;
            for (int i = 0; i < n; i++) nums.push_back(getRand(-MAX_VAL, MAX_VAL));
        }

        vector<int> ans;
        solve(n, nums, ans);
        writeInput(t, n, nums);
        writeOutput(t, n, ans);
        
        cout << "Test Case " << t << " generated (n=" << n << ")." << endl;
    }

    return 0;
}

测试点详细说明与设计意图：

1. 测试点 1 (Sample)：验证代码对基础样例的正确性。
2. 测试点 2 (Minimal)：$N=1$ 的极端边界情况。
3. 测试点 3 (Increasing)：测试单调栈在元素频繁弹出时的表现。
4. 测试点 4 (Decreasing)：重点测试“环形”功能。在递减序列中，对于 $nums[i]$，必须绕回数组开头才能找到 $nums[0]$ 作为它的更大元素。
5. 测试点 5 (Identical)：验证“大于”的严格性。如果代码错误地将“等于”判定为“更大”，此点会报错。
6. 测试点 6 (Negative)：测试对负数范围（$-10^9$）的处理，确保不会因为数值初始化问题导致逻辑错误。
7. 测试点 7 (Sawtooth)：测试栈的频繁切换，模拟波峰波谷。
8. 测试点 8 (V-Shape)：这是一种压力测试，栈会先积压大量元素，然后集中弹出。
9. 测试点 9 (Global Max)：测试当存在一个元素无解（$-1$）且其他所有元素都要绕过它寻找答案时的逻辑。
10. 测试点 10 (Full Random)：最大规模数据下的综合鲁棒性测试。

优化与安全建议：

• 内存布局：生成器中 stk 数组使用了 static 关键字。在 NOI 竞赛中，如果你的局部数组很大（超过 1MB），请务必开在全局空间或使用 static，否则会触发**栈溢出（Stack Overflow）**导致 RE。
• 非递归保证：solve 函数内部只包含循环和栈操作，不涉及任何函数递归，因此在 $N$ 达到 $10^6$ 时也是安全的。
• 数值溢出：本题输出的是元素本身而非下标，元素范围在 int 范围内，但随机生成时使用了 long long 以保证生成区间的严谨性。

你好，同学。处理环形结构（Circular Structure）是 NOI 竞赛中的高频考点。这道题在基础单调栈的基础上引入了“破环成链”的思想。

下面是按照 NOIP 竞赛标准编写的 C++14 代码，采用了手写栈和线性优化的逻辑。

【标准题解代码】

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

// 按照题意 10^4 规模，竞赛中通常会给到 10^5，我们按 10^5 开数组更稳妥
const int MAXN = 100005;

int nums[MAXN];    // 存储原数组
int ans[MAXN];     // 存储结果
int stk[MAXN * 2]; // 栈：存储下标。因为逻辑上遍历 2n 次，栈空间建议开足
int top = 0;       // 栈顶指针，0 表示栈空

int main() {
    int n;
    // 使用快读或 scanf，应对大规模数据
    if (scanf("%d", &n) != 1) return 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
        // 易错点：初始化 ans 为 -1，这样找不到更大元素的下标自然就是 -1
        ans[i] = -1; 
    }

    /*
     * 核心逻辑：逻辑上将数组延长两倍
     * 实际上不需要开 2*MAXN 的 nums 数组，只需要遍历到 2*n - 1
     * 并使用 i % n 来访问元素
     */
    for (int i = 0; i < 2 * n; i++) {
        int currentVal = nums[i % n]; // 映射回原数组下标

        // 如果当前值大于栈顶下标对应的值
        while (top > 0 && currentVal > nums[stk[top]]) {
            int prevIdx = stk[top];
            ans[prevIdx] = currentVal; // 更新该下标的“下一个更大元素”
            top--; // 弹出
        }

        // 关键点：我们只需要为前 n 个元素寻找答案
        // 虽然遍历 2n 次是为了让后面的数有机会更新前面的数，
        // 但栈里只需要存入逻辑上第一轮的下标即可（或者存入所有取模后的下标，ans 只会被更新一次）
        // 这里为了简单，只在 i < 2n 时入栈，ans 会被最新找到的更大值覆盖（符合“下一个”定义）
        if (i < 2 * n) {
            stk[++top] = i % n;
        }
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
    }

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 分析：循环从 $0$ 运行到 $2n-1$，总计执行了 $2n$ 次迭代。
• 内层分析：虽然有 while 循环，但观察 stk 的操作：
  • 在 $2n$ 次迭代中，stk[++top] 最多执行 $2n$ 次（入栈）。
  • top-- 最多执行 $2n$ 次（出栈）。
• 结论：总摊还时间复杂度为 $O(2n + 2n) = O(n)$。即使数组是环形的，我们也成功地在线性时间内解决了问题。

2. 空间复杂度：$O(n)$

• 分析：
  • nums 数组：$O(n)$
  • ans 数组：$O(n)$
  • stk 栈空间：最坏情况下（如数组单调递减），栈会存入 $n$ 个元素，空间为 $O(n)$。
• 结论：总空间为 $O(n)$，在 256MB 限制下极其安全。

三、 优化建议与易错点提醒

1. 取模运算的开销： 在极高性能要求的题目中，i % n 频繁调用会有一定开销。如果 $n$ 是常数或 $2$ 的幂次，编译器会自动优化。但在 NOI 赛场，如果你追求极致，可以写成：

   int idx = i;
   if (idx >= n) idx -= n; // 代替 idx = i % n
   

   这样可以稍微快一点点。

2. 栈内存大小： 手写栈时，数组大小要开够。虽然逻辑上栈内最多 $n$ 个元素，但因为我们遍历了 $2n$ 次，养成习惯开 2 * MAXN 可以有效避免在复杂变体题中溢出。

3. 理解“下一个”： 本题要求寻找的是第一个比自己大的数。单调栈内的元素必须保持单调递减（非严格）。即：如果遇到一个比栈顶大的数，说明栈顶的“下一个更大”找到了；如果遇到一个等于栈顶的数，直接压入栈。

4. 初始化顺序： 很多同学容易忘记初始化 ans 为 -1。在环形问题中，如果没有找到更大的数（例如全数组最大的那个数），单调栈结束时它依然会在栈里，我们必须预设它的结果为 -1。

金牌教练点评： 单调栈是“空间换时间”的典型模型。处理环形问题的核心在于“化圆为方”。当你通过遍历两次数组，利用单调栈在第二圈“补齐”第一圈未完成的任务时，你就真正理解了环形结构的线性处理精髓。