作为教练，制作滑动窗口最大值的测试数据时，核心在于构造能让单调队列频繁执行“弹出”和“保持”动作的极端序列。

本题的时间复杂度要求为 $O(n)$，因此我们的数据生成器和标准答案程序都必须严格遵守线性时间复杂度，以确保在生成 $10^5$ 级数据时不会超时。

一、 数据生成器代码 (C++14)

该程序采用非递归逻辑，利用 std::deque 维护的单调队列标程来生成对应的 .out 文件。

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

using namespace std;

// ================= 标准标程逻辑 (用于生成 .out) =================
// 使用单调队列算法，复杂度 O(n)
vector<int> get_standard_output(int n, int k, const vector<int>& nums) {
    vector<int> res;
    deque<int> dq;
    for (int i = 0; i < n; ++i) {
        // 1. 移除过期下标
        if (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        // 2. 维护单调递减性
        while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back();
        // 3. 入队
        dq.push_back(i);
        // 4. 记录答案
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

// ================= 数据生成辅助函数 =================
void write_test_case(int id, int n, int k, const vector<int>& nums) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    // 写入输入文件
    ofstream fout(in_name);
    fout << n << " " << k << "\n";
    for (int i = 0; i < n; ++i) {
        fout << nums[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算并写入输出文件
    vector<int> res = get_standard_output(n, k, nums);
    ofstream fans(out_name);
    for (int i = 0; i < res.size(); ++i) {
        fans << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    fans << endl;
    fans.close();

    cout << "Testcase " << id << " generated. (n=" << n << ", k=" << k << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    uniform_int_distribution<int> val_dist(-10000, 10000);

    for (int i = 1; i <= 10; ++i) {
        int n, k;
        vector<int> nums;

        if (i == 1) { // 样例数据
            n = 8; k = 3;
            nums = {1, 3, -1, -3, 5, 3, 6, 7};
        }
        else if (i == 2) { // 边界：k = 1
            n = 1000; k = 1;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i == 3) { // 边界：k = n
            n = 1000; k = n;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i == 4) { // 单调递增序列 (测试队列频繁弹出队尾)
            n = 50000; k = 1000;
            for (int j = 0; j < n; ++j) nums.push_back(j - 25000);
        }
        else if (i == 5) { // 单调递减序列 (测试队列长度持续增加)
            n = 50000; k = 1000;
            for (int j = 0; j < n; ++j) nums.push_back(25000 - j);
        }
        else if (i == 6) { // 全同元素 (测试判断条件 >= 还是 >)
            n = 100000; k = 500;
            nums.assign(n, 777);
        }
        else if (i <= 8) { // 随机中等规模
            n = 10000; k = rng() % n + 1;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else { // 极限规模随机
            n = 100000; k = rng() % (n / 2) + n / 4;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }

        write_test_case(i, n, k, nums);
    }
    return 0;
}

二、 测试点设计思路（创建 OJ 评测点参考）

作为教练，我们需要通过以下维度来检测选手代码的鲁棒性：

三、 考场避坑建议

1. 关于除零异常： 虽然本题不涉及除法，但在处理 i - k + 1 等下标运算时，务必注意下标不能越界。
2. 关于 I/O 性能： 当 $n=10^5$ 时，输出量也非常大。提醒学生：
   • 使用 '\n' 替代 std::endl。
   • 使用 ios::sync_with_stdio(false); cin.tie(0); 或 printf。
3. 单调队列的存储内容： 队列中必须存储下标而非数值。存储下标可以同时解决“数值比较”和“过期判断”两个问题；如果只存数值，将无法得知该数值何时离开窗口。
4. 非递归安全： 本生成器和算法完全基于迭代（Loops），不涉及任何递归调用，即便在系统栈空间极其有限的评测环境下也能稳定运行。

这份生成器生成的 .in 和 .out 文件格式严谨，可直接用于创建练习赛。加油！

你好，同学！滑动窗口最大值是 NOI 竞赛中单调队列（Monotonic Queue）的入门“板子题”。掌握了单调队列，你才能理解后续复杂的“单调队列优化 DP”等高阶算法。

以下是符合 NOI 竞赛 C++14 标准 的题解代码及详细分析。

一、 滑动窗口最大值 标程代码 (C++14)

在 NOI 考场上，为了极致的常数性能，资深选手通常会选择数组模拟双端队列。这里我先给出使用 STL deque 的版本（逻辑清晰），并在优化建议中给出数组版本。

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

/**
 * 核心逻辑：单调队列
 * 1. 队列存储的是数组的【下标】而非数值。存储下标是为了方便判断队首是否“过期”。
 * 2. 队列内部保持【单调递减】：队首永远是当前窗口内最大的。
 */

void solve() {
    int n, k;
    if (!(cin >> n >> k)) return;

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

    // dq 维护的是 a 数组的下标
    deque<int> dq;

    for (int i = 0; i < n; ++i) {
        // 关键点 1：弹出过期元素
        // 如果队首下标已经小于 i - k + 1，说明它在滑动窗口左侧外面了
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 关键点 2：保持单调性
        // 如果当前元素 a[i] 大于等于队尾元素，那么队尾元素由于“既老又弱”，
        // 在 a[i] 离开窗口前，它永远不可能成为最大值，直接踢出。
        // 注意：使用 >= 保证了队列中剩下的元素是严格单调递减的（或包含重复值，但通常 >= 更稳健）
        while (!dq.empty() && a[i] >= a[dq.back()]) {
            dq.pop_back();
        }

        // 3. 入队当前下标
        dq.push_back(i);

        // 关键点 3：输出答案
        // 当 i 增长到 k-1 时，表示第一个窗口已经形成
        if (i >= k - 1) {
            // 队首对应的元素就是当前窗口最大值
            cout << a[dq.front()] << (i == n - 1 ? "" : " ");
        }
    }
    cout << endl;
}

int main() {
    // NOI 竞赛必备：极大提升大量数据下的读写效率
    // 注意：开启后不可再使用 scanf/printf
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

二、 复杂度分析思考过程

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

• 思考过程：
  • 虽然代码里有嵌套的 while 循环，但我们不能简单地看循环嵌套层数。
  • 贡献法分析：数组中的每一个元素 $a[i]$，在整个 for 循环过程中，最多只会被 push_back 进队列一次，也最多只会被 pop_front 或 pop_back 弹出一次。
  • 因此，所有针对队列的操作总数不超过 $2n$。
  • 结论：总时间复杂度为线性 $O(n)$。

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

• 思考过程：
  • 需要 $O(n)$ 的数组存储输入数据。
  • deque 内部最多同时存储 $k$ 个元素，空间为 $O(k)$。
  • 结论：总空间复杂度为 $O(n)$。

三、 时间复杂度优化建议 (NOI 进阶)

在 NOI 这种对时间限制极其敏感的比赛中（尤其是数据量 $n > 10^6$ 时），可以进行以下优化：

1. 数组模拟双端队列 (Manual Deque)： std::deque 为了支持块状内存管理，内部逻辑复杂，常数较大。使用数组模拟可以快 2-3 倍。

   int q[1000005]; // 存储下标
   int head = 0, tail = -1;
   // 弹出过期：while (head <= tail && q[head] < i - k + 1) head++;
   // 维护单调：while (head <= tail && a[i] >= a[q[tail]]) tail--;
   // 入队：q[++tail] = i;
   // 取最大值：a[q[head]];
   

2. 避免 endl： cout << endl; 会强制刷新缓冲区，导致速度极慢。在 NOI 竞赛中请务必使用 cout << '\n';。

3. 快读 (Fast I/O)： 如果 $n$ 达到 $10^6$，即使是 ios::sync_with_stdio(false) 也有点慢。建议手写 getchar() 版本的快读函数。

四、 读题关键词总结

在 NOI 考场上，看到以下关键词要迅速联想到单调队列：

• “滑动窗口” / “连续子区间”：限定了处理范围。
• “区间最值 (Max/Min)”：单调队列的核心功能。
• “线性时间要求”：如果题目要求在 $O(n)$ 内求出所有长度为 $k$ 的区间最值。
• “动态规划优化”：如果状态转移方程形如 $dp[i] = \max(dp[j]) + val$ 且 $i-k \le j < i$，这是单调队列优化 DP 的标准模型。

教练寄语： 单调队列就像一个**“优胜劣汰”的竞技场**：新来的选手（下标 $i$）如果比你年轻且比你强，你就可以“退役”了。掌握好这个比喻，你就掌握了单调队列的精髓。加油！