“让我从此不在”和“被我捉弄一辈子”，你选哪个？ ​​​​——《擅长捉弄人的高木同学》

单调队列

如果一个选手比你小还比你强，你就可以退役了。

完全无法同台竞技。—— Nottttttthy

单调队列是一种主要用于解决滑动窗口类问题的数据结构，在长度为 的序列中，求每个长度为 的区间的最值。时间复杂度是 ，在这个问题中比 的 表和线段树要优。

直接来看如何模拟退役

单调队列的基本思想是，维护一个双向队列，遍历序列，仅当一个元素可能成为某个区间最值时才保留它。

来打个比方：

比如现在有四届选手（一般来说是初二到高二，当然我们不排除有三年级选手 提高组的可能），一开始的时候高一和高二的学长实力较菜，初三的最强，而初二的选手因为还有机会成为最强所以保留：

退役

一年过去了，原本初二的变成初三，却发现新来的初二老强了，自己没有机会成为最大值，直接原地退役：

AFO

又过了一年，新进机房的初二同学虽然能力值只有 ，但是理论上只要后面的人能力值是负数，那他就还能嚣张一段时间，所以入队：

引退

结果……这一年进机房的初二大佬是最强的，能力值直接飙到了 ，其他所有人都没有机会了，全体退役：

reducta

总之，观察后就能发现我们维护的这个队列是单调递减的，当然如果你想单调递增我也不拦着你，这就是为什么叫做单调队列。

给出代码：

1
2
3
4
5
6
7
8
9
10
11
deque <int> Q; // 双端队列 
for (int i = 1; i <= n; i ++)
{
	if (!Q.empty () && i - Q.front () >= m) // 队列是有长度的  
		Q.front (); // 删除掉过期的元素，即毕业 
	while (!Q.epmty () && a[Q.back ()] < a[i]) // 新进来的比当前队列中最后一位强  
		Q.pop_back (); // 从队列的后面往前逐个弹出原地退役的选手 
	Q.push_back (i); // 存入编号 
	if (i >= m - 1)
		printf ("%d ", a[Q.front ()]); 
}

单调队列可以用于 优化，但是我们不会在这里讲它。

例题

滑动窗口

有一个长为 的序列和一个大小为 的窗口。现在这个窗口从左边往右边滑动，每次滑动一个单位，求每次窗口中的最大值和最小值。

究极模板了这已经，维护两个单调队列，一个递增，一个递减，只要改一个小小的地方就可以了，代码奉上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;

int n, k, a[N], Ans[N], ans[N], Cnt, cnt;

deque <int> Q;
deque <int> q;

int main ()
{
	scanf ("%d %d", &n, &k);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%d", &a[i]);
		while (!Q.empty () && i - Q.front () >= k)
			Q.pop_front ();
		while (!q.empty () && i - q.front () >= k)
			q.pop_front ();
		while (!Q.empty () && a[Q.back ()] < a[i])
			Q.pop_back ();
		while (!q.empty () && a[q.back ()] > a[i])
			q.pop_back ();
		Q.push_back (i);
		q.push_back (i);
		if (i >= k)
		{
			Ans[++ Cnt] = a[Q.front ()];
			ans[++ cnt] = a[q.front ()];
		}
	}
	for (int i = 1; i <= cnt; i ++)
		printf ("%d ", ans[i]);
	puts ("");
	for (int i = 1; i <= Cnt; i ++)	
		printf ("%d ", Ans[i]);
	return 0;
}