【GESP】C++五、六级练习题 luogu-P1886 【模板】单调队列 / 滑动窗口

GESP C++ 五、六级及以上水平练习题，考查单调队列知识点。本题是经典的滑动窗口求解区间最值的模板题，对于降低时间复杂度有着重要意义，推荐五、六级以上考生练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1886 【模板】单调队列 / 滑动窗口

题目要求

题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。

例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程：

\[\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}\]

输入格式

输入一共有两行，第一行有两个正整数 $n,k$；

第二行有 $n$ 个整数，表示序列 $a$。

输出格式

输出共两行，第一行为每次窗口滑动的最小值；

第二行为每次窗口滑动的最大值。

输入输出样例 #1

输入 #1

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

输出 #1

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

说明/提示

【数据范围】

对于 $50\%$ 的数据，$1 \le n \le 10^5$；

对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。

---

题目分析

这道题的核心考点是求滑动窗口中的最大值和最小值。对于长为 $n$ 的序列，窗口大小为 $k$，如果使用朴素的扫描算法，每次都在窗口内遍历求最值，时间复杂度为 $O(n \times k)$。在本题 $n \le 10^6$ 的数据规模下，最坏运算次数将达到 $10^{12}$ 次，绝对会导致程序在评测时出现 超时 (Time Limit Exceeded, TLE) 报错。

为了能够全对通过此题，我们需要时间复杂度为 $O(n)$ 的高效算法——单调队列 (Monotonic Queue)。

1. 什么是单调队列？

单调队列是一种双端队列，它的内部元素在任何时候都保持着单调递增或单调递减的性质。

以求滑动窗口的 最小值 为例，我们需要维护一个 单调递增 的队列：

• 当一个新元素准备入队时，如果它比队尾元素更小，那么原本的队尾元素在这个新元素存在的整个周期内，都不可能成为更优解（最小值）。因此，我们可以放心地将队尾元素弹出，直到队列为空或队尾元素小于新元素为止，然后再将新元素入队。
• 随着窗口滑动，队首元素可能已经不在当前长度为 $k$ 的窗口内了，此时需要将过期元素从队首淘汰出局。
• 因为我们维护的是递增序列，所以合法的队首元素永远保存着当前窗口的最小值。

我们以序列 [1, 3, -1, -3, 5, 3, 6]，窗口大小 $k=3$ 为例，模拟单调递增队列（求最小值）的运作过程。为了能够既直观又严谨地展示，我们分别列出队列内存放的元素索引和其对应的实际数值：

• 处理 1 (原数组索引 0)：队列为空，直接入队。队列状态：索引 [0]，对应数值 [1]。
• 处理 3 (原数组索引 1)：3 大于队首对应的队尾元素 1，满足递增，3 的索引入队。队列状态：索引 [0, 1]，对应数值 [1, 3]。
• 处理 -1 (原数组索引 2)：新元素 -1 (< 队尾 3) 准备入队。因为 -1 比 3 晚进入窗口，且值更小，只要 -1 还在窗口内，3 就永远不可能成为更优的最小值。因此 3 对应的索引被放心淘汰出队。同理，1 也被淘汰出队。最后 -1 的索引入队。队列状态：索引 [2]，对应数值 [-1]。此时前三个元素处理完毕，恰好凑足第一个窗口大小 $k=3$，输出队首对应的最小值 -1。
• 处理 -3 (原数组索引 3)：-3 (< 队尾 -1)，淘汰 -1，-3入队。队列状态：索引 [3]，对应数值 [-3]。输出这一个窗口的最小值 -3。
• 处理 5 (原数组索引 4)：5 (> 队尾 -3)，满足递增。队列状态：索引 [3, 4]，对应数值 [-3, 5]。输出这一个窗口的最小值 -3。
• 处理 3 (原数组索引 5)：3 (< 队尾 5)，淘汰 5。队列状态：索引 [3, 5]，对应数值 [-3, 3]。输出这一个窗口的最小值 -3。
• 处理 6 (原数组索引 6)：重点来了！此时滑动窗口对应的数组元素是 [5, 3, 6]（原数组索引 $[4, 5, 6]$）。队首依然存着索引 3，但索引 3 已经掉出了当前窗口的范围（$3 \le 6 - 3$），所以索引 3 记录的元素 -3 已经“过期”，必须从队首淘汰出局。随后 6 (> 队尾 3)，正常入从队尾队。队列状态：索引 [5, 6]，对应数值 [3, 6]。由于过期的 -3 被移出，此时输出这一个窗口真正的最小值 3。

2. 算法核心步骤

1. 维护元素索引：为了方便判断队首元素是否滑出窗口并过期，单调队列里面存储的通常不是具体的数值，而是元素在原数组中的位置索引 (下标)。
2. 队尾入队 (剔除劣解)：对于新加入的元素 $a[i]$，只要队尾索引所对应的元素大于等于 $a[i]$，队首一直到原队尾维护的递增关系就会被打破，并且之前的那些大元素在 $a[i]$ 存活时毫无竞争优势。直接将它们从队尾弹出，直到满足单调性，然后将当前索引 $i$ 从队尾压入。
3. 队首出队 (剔除过期元素)：队首元素虽然是当前队列中最小的，但如果它的索引位于 $i - k$ 甚至更早（即超出了长度为 $k$ 的窗口，合法范围应该是 $[i - k + 1, i]$），就需要将其从队首弹出淘汰。
4. 获取答案：当处理完前 $k$ 个元素，第一个完整窗口才初建完成。之后每次处理一个新元素并更新队列后，队首所对应的元素即为当前窗口的最小值。

求 最大值 的逻辑完全一致，只需维护一个 单调递减队列。遇到比队尾大或相等的元素就弹出队尾，最后淘汰过期队首元素，合法的队首元素即为滑动窗口的最大值。

---

示例代码

#include <iostream>

// 数据规模最大为 1000000
const int MAXN = 1000005;

int ary[MAXN];
// 单调队列中存储的是数组元素的下标索引
int q[MAXN];

int main() {
    // 提升 cin cout 的读写速度，防止在读入海量数据时卡常超时
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    // 依次读入 n 个元素
    for (int i = 0; i < n; ++i) {
        std::cin >> ary[i];
    }

    // ========== 1. 求解滑动窗口的最小值 ==========
    int head = 0; // 队首指针
    int tail = 0; // 队尾指针（指向下一个要插入的位置）

    for (int i = 0; i < n; ++i) {
        // 第一步：队首出队 (剔除过期元素)
        // 如果队列不空，并且队首记录的下标已经超出了滑动窗口的合法范围 [i-k+1, i]，则队首出队
        if (head < tail && q[head] <= i - k) {
            head++;
        }

        // 第二步：队尾入队 (维护单调递增性)
        // 如果队列不空，并且队尾元素的值大于或等于准备入队的新元素的值
        // 那么队尾元素就不可能成为以后的最小值，将其从队尾弹出，让位给更小的新元素
        while (head < tail && ary[q[tail - 1]] >= ary[i]) {
            tail--;
        }

        // 此时队尾没有比新元素更大的值了，将新元素的下标即可安全入队
        q[tail] = i;
        tail++;

        // 第三步：输出答案
        // 当索引 i 大于等于 k-1 时，说明第一个完整的窗口已经形成，以后每一次循环都要输出队首指代的最小值
        if (i >= k - 1) {
            std::cout << ary[q[head]] << " ";
        }
    }
    std::cout << "\n";

    // ========== 2. 求解滑动窗口的最大值 ==========
    // 重新初始化队列头尾指针，清空队列
    head = 0;
    tail = 0;

    for (int i = 0; i < n; ++i) {
        // 第一步：队首出队 (剔除过期元素)
        if (head < tail && q[head] <= i - k) {
            head++;
        }

        // 第二步：队尾入队 (维护单调递减性)
        // 求最大值时，需要淘汰队尾所有比新元素小(或相等)的元素，给更有潜力成为最大值的新元素腾出空间
        while (head < tail && ary[q[tail - 1]] <= ary[i]) {
            tail--;
        }

        // 淘汰完毕，新元素的下标从队尾入队
        q[tail] = i;
        tail++;

        // 第三步：输出答案
        if (i >= k - 1) {
            std::cout << ary[q[head]] << " ";
        }
    }
    std::cout << "\n";

    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号