单调队列

滑动窗口（题目链接）

分析

仅以最小值为例，根据样例进行分析 1 3 -1 -3 5 3 6 7 以k为步长，在取值的过程中-1比-3先入队，所以有-3的地方一定会存在-1 又因为每次均取得最小值，故-3在的情况下-1永远不可能作为答案输出 所以，-3进队的时候可以将-1出队 重复此过程即可形成单调递增队列，每次取队列头即可渠道每个窗口的最小值

代码

数组模拟队列，在此法中，队列中存储的是原数组的下标

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; int a[N], q[N]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int hh = 0, tt = -1; //初始化队列,完成最小值查找 for (int i = 0; i < n; i++) { if (hh <= tt && i - k + 1 > q[hh]) //删除不在窗口内的数字 hh++; while (hh <= tt && a[q[tt]] >= a[i]) //将小于当前队尾的数的下表过滤掉 tt--; q[++tt] = i; //将大于当前队尾的数的下标入队 if (i >= k - 1) printf("%d ", a[q[hh]]); } cout << endl; hh = 0, tt = -1; //初始化队列,完成最大值查找 for (int i = 0; i < n; i++) {a if (hh <= tt && i - k + 1 > q[hh]) hh++; while (hh <= tt && a[q[tt]] <= a[i]) tt--; q[++tt] = i; if (i >= k - 1) printf("%d ", a[q[hh]]); } cout << endl; return 0; }

此题用c++封装的队列不易实现，因为要不断访问前一个入队的元素，会浪费很多的的存储空间，并且无法对队列执行逆向出队的操作。