零.前言
很明显的，本题是单调队列的模板题目。
为了方便我（和来赏光的 \(julao\) ）今后复习，写一篇题解。
例题：
壹.简述
单调队列是一种数据结构（不知道算不算基础数据结构）
它满足一下性质：
- 单调队列中的数是满足单调递增/递减/或是其他的性质
- 单调队列中的数的下标是单调递增的（这也是下面的几位 \(julao\) 将单调队列与优先队列混为一谈的错误之处了，优先队列会将下标改变）
贰.对于本题的分析
本题很明显是使用单调队列求窗口中得最大值与最小值得。
什么是窗口呢？
（虽然我只是口胡。。。反正窗口挺好理解的吧，，口胡这么多大家别绕晕了，就是你理解的那个窗口）
窗口是指：在一段序列中，从下标为 \(i\) 到下标为 \(i + k - 1\) 的下标连续的子序列。其中 \(k\) 为窗口大小。滑动窗口是指 \(i\) 会滑动，也就是递增或递减，从而使得整个子序列的长度不变，但涵盖的数变化了。
形象的讲，就是在一段子序列右端点随着左端点的增大而增大。
叁.对于单调队列的分析
单调队列有两个操作：删头和去尾（这两的名字是来源于）
(为了方便理解，本题当中的头是指最后进来的数所在的位置，尾为最先进来的数所在的位置)
一 去尾
很明显，本题的是有窗口的，也就是说，我们的单调队列中的数的下标，不仅要递增，而且不能过期。
所以每次我们更新队头的时候，都要判断队尾的下标是否过期了。只要队尾的下标过期，即在以当前更新到的数为头的窗口外，就 \(pop\) 出去。
while (q.back().n <= i - k) q.pop_back(); // i 为当前的队头的下标， k 为窗口大小
(本题的单调队列用结构体来写的，结构体中的 \(m\) 代表值， \(n\) 代表下标)
二 删头
对于序列当中的每一个数都会更新一次。刚刚的去尾是维护单调队列下标的性质，现在我们来维护一下单调队列的递增性。
定义队头的数为 \(x\)，更新到的数为 \(y\)
我们要维护一个单调递增的队列，也就是说对于队列中的所有数，下标比它大的值也比它大。
我们要维护一个窗口中最小值，要用单调递增的队列，因为队尾是最小的值。
第一种情况： \(y > x\)
那就直接放入，因为这样不破坏数的单调性，放入这个数后队列依然是递增的第二种情况： \(y < x\)
首先肯定不能直接放入，因为放入后单调性就会被破坏。首先，这个数比当前队头的数的下标要大，值却比它小。所以在 $x$ 的有生之年内，都不可能是窗口最小(或满足所求)的。因为我们已经更新到了 $y$，所以只要包括 $x$ 的窗口一定包括了 $y$，而且 $x > y$，所以一直到 $x$ 过期，他都不可能是最小的数。也就是说，一个数比你晚进来（下标比你大）还比你更满足我们要求的数的性质，那你就打不过他了。打不过怎么办，直接pop掉啊（好残忍）
上代码
while (!q.empty() && a[i].m <= q.front().m) q.pop_front(); // a为给出的序列，m和n的意义如上
所以经过我们刚才的分析，单调队列的通用模板如下：
while (!q.empty() && a[i].m 更符合所求的要求 q.front().m) q.pop_front();q.push_front(a[i]); // 现在的队头打得过更新到的数了while (q.back().n <= i - k) q.pop_back();printf("%d", q.back().m); // 队尾的是当前最符合要求的数，为什么呢？看下面 三 性质
刚才的两个操作分析完了，我们来分析一下那个是最符合性质的数。
每一个数都比后一个数更符合性质
所以就是第一个数了。
四 完整代码
#includeusing namespace std;const int maxn = 1e6 + 10;int all, k;struct node { int n, m; }a[maxn];deque q;void BIG(int all, int k) { for (int i = 1; i <= all; ++i) { while (!q.empty() && a[i].m >= q.front().m )q.pop_front(); // 求最小的 q.push_front(a[i]); while (q.back().n <= i - k) q.pop_back(); if (i >= k) printf("%d ", q.back().m); } q.clear();}void LOW(int all, int k) { for (int i = 1; i <= all; ++i) { while (!q.empty() && a[i].m <= q.front().m) q.pop_front(); // 求最大的 q.push_front(a[i]); while (q.back().n <= i - k) q.pop_back(); if (i >= k) printf("%d ", q.back().m); } q.clear();}int main() { scanf("%d %d", &all, &k); for (int i = 1; i <= all; ++i) scanf("%d", &a[i].m), a[i].n = i; LOW(all, k); puts(""); BIG(all, k); return 0;}
代码部分参考了楼下 \(julao\) 的代码，有点抄题解的嫌疑
（题解的事情，能叫抄题解吗）
4.茶余饭后
有一天，有一个叫
的 \(julao\) 进入了一个叫“国家队”的单调队列。
然后，单调队列中所有的数除了 都被清空了。
包括我这个 \(juruo\)
很久以后，人们才敢回想起被小光支配的恐惧。
~~qwq~
如果你觉得这篇文章对你有所帮助，欢迎点击推荐！