你好，同学！欢迎来到 NOI 专题训练。

今天我们要攻克的是数据结构进阶中的“镇山之石”：滑动窗口最大值。这道题是学习**单调队列（Monotonic Queue）**的必经之路。在 NOI 竞赛中，单调队列常用于优化动态规划（DP），是提升程序效率的利器。

一、 预备知识点

1. 双端队列（Deque）：支持在两端进行 $O(1)$ 插入和删除。
2. 单调性维护：通过特定规则，使队列中的元素始终保持单调递增或递减。
3. 滑动窗口：一个长度固定的区间在序列上移动。

二、 NOI 竞赛题目描述

题目名称：滑动窗口最大值 (Sliding Window Maximum) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个长度为 $n$ 的整数数组 $nums$，有一个长度为 $k$ 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 $k$ 个数字。滑动窗口每次只向右移动一位。 请输出一个数组，包含窗口每次移动时，窗口内的最大值。

【输入格式】 第一行包含两个整数 $n$ 和 $k$。 第二行包含 $n$ 个整数，表示数组 $nums$。

【输出格式】 输出一行，包含 $n - k + 1$ 个整数，用空格分隔。

【样例输入】

8 3
1 3 -1 -3 5 3 6 7

【样例输出】

3 3 5 5 6 7

【数据规模与约定】

• $1 \le n \le 10^5$
• $1 \le k \le n$
• $-10^4 \le nums[i] \le 10^4$

三、 启发式思路：草稿纸上的推演（“祛除老弱”法）

请在草稿纸上画出窗口移动的过程。我们要寻找一种方法，不需要每次移动都重新遍历窗口（那将是 $O(nk)$，在本题 $10^{10}$ 的量级下会超时）。

1. 核心矛盾

如果窗口里有两个人：A 比 B 年轻（位置更靠后），且 A 比 B 强（数值更大），那么只要 A 在窗口里，B 就永远不可能成为最大值。

• 启发：B 可以直接被“踢出”候选名单。

2. 模拟推演

假设 $nums = [1, 3, -1, -3, 5, 3], k=3$。维护一个单调递减队列（存放下标）：

1. 遇到 1：队列为空，存入下标 0。 队列：{0} (对应值 1)
2. 遇到 3：3 比 1 大。1 既比 3 老又比 3 弱，踢出。存入下标 1。 队列：{1} (对应值 3)
3. 遇到 -1：-1 比 3 小。虽然 -1 弱，但它更“年轻”，在 3 离开后它可能有机会当老大。存入下标 2。 队列：{1, 2} (值 3, -1)
   • 此时窗口满 3 个，输出队首 nums[1] = 3。
4. 遇到 -3：-3 比 -1 小。存入下标 3。 队列：{1, 2, 3}
   • 检查队首：下标 1 是否还在窗口 [1, 3] 内？在。输出队首 nums[1] = 3。
5. 遇到 5：5 比 -3, -1, 3 都强。它们全是“老弱”，全部踢出。存入下标 4。 队列：{4} (值 5)
   • 输出 nums[4] = 5。

四、 算法流程图（伪代码逻辑）

graph TD
    Start(开始遍历数组下标 i) --> OutWindow{队首下标是否过期}
    OutWindow -- 是 --> PopFront(弹出队首 front)
    OutWindow -- 否 --> Maintain(进入单调维护)
    PopFront --> Maintain
    
    Maintain --> WhileLoop{队列不为空 且 当前值大于等于队尾值}
    WhileLoop -- 是 --> PopBack(弹出队尾 back)
    PopBack --> WhileLoop
    WhileLoop -- 否 --> PushBack(当前下标 i 入队)
    
    PushBack --> CheckPrint{当前 i 是否达到窗口长度 k 减 1}
    CheckPrint -- 是 --> Print(输出队首下标对应的值)
    CheckPrint -- 否 --> Next(继续循环)
    Print --> Next
    Next --> LoopEnd{遍历结束}

五、 NOI 标准题解代码 (C++14)

见题解

六、 时间复杂度优化建议

1. 手动模拟双端队列： std::deque 的常数较大。在 NOI 考场上，若 $N=10^6$ 且时限紧，建议用数组模拟队列：

   int q[100005], head = 0, tail = -1;
   // 入队: q[++tail] = i;
   // 出队: head++;
   // 队尾弹出: tail--;
   

2. 避免频繁输出： 如果输出量巨大，可以使用 '\n' 代替 endl（endl 会强制刷新缓冲区，极慢），或使用 printf。

七、 读题关键词总结

• “连续子数组 / 窗口”：提示可能使用滑动窗口。
• “窗口内的最大值/最小值”：这是单调队列的经典信号。
• “$O(n)$ 时间复杂度”：如果题目要求线性时间处理最值，基本确定是单调队列。

教练寄语：单调队列的核心在于“喜新厌旧”——新的如果还比旧的强，旧的就彻底没用了。掌握了这个逻辑，你就能处理所有滑动窗口最值问题。加油！