滑动窗口单调队列

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

要构造单调递增以及单调递减队列，分别按以下思路进行： $$递增队列（输出最小值）\{\begin{array}{l}若待插入队列的元素小于队尾元素，则弹出队尾元素直到待插入元素大于等于队尾元素为止\\ \\ 若待插入元素大于等于队尾元素，则直接插入该元素\end{array}$$ $$递减队列（输出最大值）\{\begin{array}{l}若待插入队列的元素大于队尾元素，则弹出队尾元素直到待插入元素小于等于队尾元素为止\\ \\ 若待插入元素小于等于队尾元素，则直接插入该元素\end{array}$$

#include <cstdio> #include <cstring> const int maxn = 1000005; struct monque { int n, k, head, tail; int a[maxn], q[maxn], p[maxn]; void read() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); } void monque_min() { head = 1; tail = 0; for (int i = 1; i <= n; i++) { while (head <= tail && q[tail] >= a[i]) tail--; q[++tail] = a[i]; p[tail] = i; while (p[head] <= i - k) head++; if (i >= k) printf("%d ", q[head]); } printf("\n"); } void monque_max() { head = 1; tail = 0; for (int i = 1; i <= n; i++) { while (head <= tail && q[tail] <= a[i]) tail--; q[++tail] = a[i]; p[tail] = i; while (p[head] <= i - k) head++; if (i >= k) printf("%d ", q[head]); } printf("\n"); } } Monque; int main() { Monque.read(); Monque.monque_min(); Monque.monque_max(); return 0; }

参考 https://www.luogu.com.cn/blog/hankeke/solution-p1886