作为教练，制作滑动窗口最值类题目数据时，核心在于构造能够让窗口频繁“伸缩”以及让单调队列频繁“换届”的序列。

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

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

该程序采用非递归逻辑，利用双单调队列（Deque）实现的 $O(N)$ 标程来生成对应的 .out 文件。

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

using namespace std;

/**
 * 标程逻辑：用于生成 .out 文件
 * 使用双单调队列实现 O(N) 解法
 */
int solve_standard(int n, int limit, const vector<int>& nums) {
    deque<int> max_dq, min_dq;
    int left = 0, ans = 0;
    for (int right = 0; right < n; ++right) {
        while (!max_dq.empty() && nums[right] > nums[max_dq.back()]) max_dq.pop_back();
        while (!min_dq.empty() && nums[right] < nums[min_dq.back()]) min_dq.pop_back();
        max_dq.push_back(right);
        min_dq.push_back(right);

        while (nums[max_dq.front()] - nums[min_dq.front()] > limit) {
            left++;
            if (max_dq.front() < left) max_dq.pop_front();
            if (min_dq.front() < left) min_dq.pop_front();
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

/**
 * 写入测试点文件
 */
void write_test_case(int id, int n, int limit, const vector<int>& nums) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

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

    // 计算并写入输出文件 (.out)
    int result = solve_standard(n, limit, nums);
    ofstream fans(out_name);
    fans << result << endl;
    fans.close();

    cout << "Generated Case " << id << " (N=" << n << ", limit=" << limit << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    uniform_int_distribution<int> val_dist(1, 1e9);

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

        if (i == 1) { // 样例 1
            n = 4; limit = 4;
            nums = {8, 2, 4, 7};
        } 
        else if (i == 2) { // 样例 2
            n = 6; limit = 5;
            nums = {10, 1, 2, 4, 7, 2};
        }
        else if (i == 3) { // 边界点：N=1, limit=0
            n = 1; limit = 0;
            nums = {1000};
        }
        else if (i == 4) { // 全等数据：ans = N
            n = 5000; limit = 100;
            nums.assign(n, 500);
        }
        else if (i == 5) { // 极限波动：每个元素差值都很大
            n = 5000; limit = 1;
            for (int j = 0; j < n; ++j) nums.push_back(j % 2 == 0 ? 1 : 1e9);
        }
        else if (i == 6) { // 单调递增序列
            n = 50000; limit = 1000;
            for (int j = 0; j < n; ++j) nums.push_back(j * 10);
        }
        else if (i == 7) { // 单调递减序列
            n = 50000; limit = 1000;
            for (int j = 0; j < n; ++j) nums.push_back(1e9 - j * 10);
        }
        else if (i == 8) { // 随机中等规模
            n = 10000; limit = 1e6;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i <= 10) { // 极限规模 N=10^5 随机
            n = 100000; limit = 1e8;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }

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

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

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

三、 考场避坑建议

1. 关于除零异常： 本题不涉及除法。但在计算 right - left + 1 或 max_dq.front() - min_dq.front() 时，确保逻辑中队列非空（!max_dq.empty()），避免非法访问。

2. 数值溢出： 虽然 $nums[i] \le 10^9$，int 不会溢出。但在计算两个数的差值并与 limit 比较时，如果是其他类似题目涉及乘法或更大数据，务必使用 long long。

3. 单调队列的存储内容： 必须存储下标而非数值。存储下标是处理“过期”最直接的方法。如果只存数值，在 left 右移时你无法判断当前的 max 是否就是被移出的那个。

4. 非递归安全： 本生成器和算法完全基于迭代（Loops），不涉及任何递归调用。即便在系统栈空间极其有限的评测环境下（如某些旧版 NOI 评测机），也能稳定运行。

这份生成器生成的 .in 和 .out 文件可以直接上传到任何标准 OJ（如 HUSTOJ, Hydro, Vijos 等）。加油！

你好，同学。这道题是单调队列（Monotonic Queue）的高级应用。在 NOI 竞赛中，它常被用作复杂动态规划（DP）的优化手段。本题的关键在于：如何高效地维护一个滑动窗口内的最大值和最小值。

以下是符合 NOIP/NOI 竞赛 C++14 标准 的满分题解代码。

一、 标程代码（C++14 标准）

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

using namespace std;

/**
 * 核心思路：滑动窗口 + 双单调队列
 * 1. 使用 left 和 right 维护滑动窗口。
 * 2. max_dq（单调递减队列）：队首始终是当前窗口内的最大值。
 * 3. min_dq（单调递增队列）：队首始终是当前窗口内的最小值。
 * 4. 当 max_dq.front() - min_dq.front() > limit 时，收缩左指针 left。
 */

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

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

    // 存储下标而非数值，方便根据 left 指针判断是否过期
    deque<int> max_dq, min_dq;
    int left = 0, ans = 0;

    for (int right = 0; right < n; ++right) {
        // 1. 维护最大值队列（递减）：新来的数如果更大，队尾就没用了
        while (!max_dq.empty() && nums[right] > nums[max_dq.back()]) {
            max_dq.pop_back();
        }
        max_dq.push_back(right);

        // 2. 维护最小值队列（递增）：新来的数如果更小，队尾就没用了
        while (!min_dq.empty() && nums[right] < nums[min_dq.back()]) {
            min_dq.pop_back();
        }
        min_dq.push_back(right);

        // 3. 检查当前窗口是否合法
        // 如果 最大值 - 最小值 > limit，说明窗口必须收缩
        while (!max_dq.empty() && !min_dq.empty() && 
               nums[max_dq.front()] - nums[min_dq.front()] > limit) {
            left++;
            // 如果队首下标已经小于新的 left，说明该最值已不在窗口内，弹出
            if (max_dq.front() < left) max_dq.pop_front();
            if (min_dq.front() < left) min_dq.pop_front();
        }

        // 4. 更新全局最长长度
        ans = max(ans, right - left + 1);
    }

    cout << ans << endl;
}

int main() {
    // NOI 竞赛必备优化：加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

二、 复杂度分析思考过程

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

• 推演：虽然代码中存在 while 嵌套，但请注意观察 left 指针和 right 指针。
  • right 指针从 $0$ 移动到 $n-1$。
  • 每个元素在每个单调队列中，最多只会被 push_back 一次，也最多只会被弹出一次（pop_back 或 pop_front）。
  • 因此，整个双指针移动过程中，所有队列操作的总次数是 $O(n)$。
• 结论：总时间复杂度为线性 $O(n)$。

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

• 推演：需要 $O(n)$ 存储输入数组，单调队列在最坏情况下（如单调递增或递减序列）会存储 $O(n)$ 个元素。
• 结论：总空间复杂度为 $O(n)$。

三、 考场避坑点与优化建议

1. 易错点（Bug 预警）

• 队列存储内容：一定要存储下标（Index）而不仅仅是数值。只有存储下标，当左指针 left 移动时，你才能判断队首的最值是否还在当前窗口覆盖范围内。
• 条件判断顺序：在收缩窗口的 while 循环中，必须先执行 left++，再判断队首下标是否过期。
• 数值溢出：本题 nums[i] 最高 $10^9$，int 足以胜任。但如果 nums[i] 达到 $10^{15}$，必须全线更换为 long long，且 limit 也要相应提升。

2. 时间复杂度优化建议（NOI 进阶）

• 手动模拟队列 (Static Array)：std::deque 是一个分段连续的容器，其 pop_front 的常数较大。在 $n=10^6$ 的极限压力测试中，建议手写数组模拟队列：

  int q_max[100005], head_max = 0, tail_max = -1;
  // 入队: q_max[++tail_max] = right;
  // 弹出队首: head_max++;
  

  这种写法比 STL 容器快约 3-5 倍。
• 平衡树替代方案：你也可以使用 std::multiset<int> 来维护窗口内的最值（*s.rbegin() - *s.begin()）。这种写法的时间复杂度是 $O(n \log n)$。虽然在 $10^5$ 规模下能过，但在 NOI 考场上，如果时限紧，它可能会因为常数过大而导致 TLE（超时）。单调队列是此类问题的标准线性解。

教练寄语：这道题是双指针和单调队列的完美结合。如果你能理解为什么**“只要有了更年轻且更强的元素，旧的弱元素就没用了”**，你就真正掌握了单调队列。去实现它吧！