【题目来源】
洛谷：P1886 【模板】单调队列 / 滑动窗口 - 洛谷
【题目描述】
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 [1,3,−1,−3,5,3,6,7] 以及 k=3，有如下过程：
【输入】
输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数，表示序列 a
【输出】
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
【输入样例】
8 3
1 3 -1 -3 5 3 6 7
【输出样例】
-1 -3 -3 -3 3 3
3 3 5 5 6 7
【算法标签】
《洛谷 P1886 单调队列》 #模拟# #线段树# #单调队列# #队列#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
int a[N], q[N]; // a: 输入数组, q: 单调队列（存储下标）
int n, k; // n: 数组长度, k: 滑动窗口大小int main()
{cin >> n >> k; // 读入n和k// 读入数组for (int i = 1; i <= n; i++)cin >> a[i];// 第一部分：维护窗口最小值int h = 1, t = 0; // h: 队头指针, t: 队尾指针, 初始队列为空for (int i = 1; i <= n; i++) {// 维护队列单调递增// 当队列非空且队尾对应的值 >= 当前值时，弹出队尾while (h <= t && a[q[t]] >= a[i]) t--;// 将当前下标加入队尾q[++t] = i;// 如果队头元素已经不在当前窗口内，弹出队头if (q[h] < i - k + 1) h++;// 当窗口形成时（i >= k），输出当前窗口的最小值if (i >= k) cout << a[q[h]] << " ";}cout << endl;// 第二部分：维护窗口最大值h = 1, t = 0; // 重置队列for (int i = 1; i <= n; i++) {// 维护队列单调递减// 当队列非空且队尾对应的值 <= 当前值时，弹出队尾while (h <= t && a[q[t]] <= a[i]) t--;// 将当前下标加入队尾q[++t] = i;// 如果队头元素已经不在当前窗口内，弹出队头if (q[h] < i - k + 1) h++;// 当窗口形成时（i >= k），输出当前窗口的最大值if (i >= k) cout << a[q[h]] << " ";}cout << endl;return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, k, a[N], q[N]; // a: 输入数组, q: 单调队列(存储下标)
int main()
{cin >> n >> k; // 读入数组长度和窗口大小// 读入数组元素for (int i = 1; i <= n; i++) cin >> a[i];// 第一部分：求滑动窗口最小值int hh = 0, tt = -1; // 队列初始化: hh-队头, tt-队尾, 空队列时hh>ttfor (int i = 1; i <= n; i++){// 1. 维护窗口范围: 如果队头元素不在窗口内，弹出队头if (hh <= tt && q[hh] < i - k + 1) hh++;// 2. 维护队列单调性: 保持队列单调递增while (hh <= tt && a[q[tt]] >= a[i]) tt--;// 3. 当前下标入队q[++tt] = i;// 4. 当窗口形成时，输出当前窗口最小值(队头元素)if (i >= k) cout << a[q[hh]] << " "; }cout << endl;// 第二部分：求滑动窗口最大值hh = 0, tt = -1; // 重置队列for (int i = 1; i <= n; i++){// 1. 维护窗口范围if (hh <= tt && q[hh] < i - k + 1) hh++;// 2. 维护队列单调性: 保持队列单调递减(求最大值)while (hh <= tt && a[q[tt]] <= a[i]) tt--;// 3. 当前下标入队q[++tt] = i;// 4. 当窗口形成时，输出当前窗口最大值(队头元素)if (i >= k) cout << a[q[hh]] << " ";}cout << endl;return 0;
}
【运行结果】
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7