单调队列的思想及应用

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

思想及实现

定义

单调队列，就是有单调性的队列。

举例

对于一个无序数组，以维护单调递减队列为例，例如$7,3,9,1,8,5,4,2$，我们将其一个一个插入队列，将得到一个形如$9,8,5,4,2$的队列。

如何理解开篇那句话？$9$比前面2个数都要小（比前面的数强），把出现的顺序比作出生的顺序，于是乎，前面的数就被迫出队（退役）。

如何维护

在插入操作时，保证队列的单调性，以单调递减队列为例：

在插入时，假设插入的元素为x，当队尾元素的大小等于x时，直接插入即可
当队尾元素的小于等于x时，先不断尝试弹出队尾元素，知道队列为空或者队尾元素的大小大于x时，再进行插入

故，只要插入之前弹出影响单调性的元素，再插入所需插入的元素

入队代码实现：

int q[N], hh = 0, tt = -1;
void push(int x) {
    while (tt >= hh && tt) tt --;
    q[++ tt] = x;
}

与单调栈的区别

如果没有左边界，考虑单调栈，如果有左边界，考虑单调队列。

模板题

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题不完全是板子题，我们的队列里要维护下标而不是原数组中的值。这样一来，我们就可以根据下标把移出左边界的数出队，同时，又能利用下标来确定原数组中元素的值。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1e6+10;
int a[maxn],q[maxn],n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int h=1,t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&q[h]+k<=i)h++;	// 维护左边界
		while(h<=t&&a[i]<a[q[t]])t--;	// 保证单调性，和单调栈类似
		q[++t]=i;	// 入队
		if(i>=k&&i<n)printf("%d ",a[q[h]]);
		else if(i>=k)printf("%d\n",a[q[h]]);
	}
	h=1;t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&q[h]+k<=i)h++;
		while(h<=t&&a[i]>a[q[t]])t--;
		q[++t]=i;
		if(i>=k&&i<n)printf("%d ",a[q[h]]);
		else if(i>=k)printf("%d\n",a[q[h]]);
	}
	return 0;
}