单调队列

单调队列是一个类似于单调栈的知识点，都是通过维护单调性用 $O(n)$ 的时间求解前面的数据对后面的数据没有影响的问题。

和单调栈差不多，但是单调队列使用的是栈而不是队列。其中使用队头来维护数据，队尾来维护单调性。

对于P1886 【模板】单调队列 / 滑动窗口，可以使用单调队列维护下标，因为用值不可以知道下标，但用下标可以知道值。

具体操作如下： 当队列非空时，且窗口是大于理想大小，就

head++

a[i]

tail--

注意点 1.要特判大小大于等于窗口大小，也就是

i>=k

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int n,k;
int q[N];
int head=1,tail;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(head<=tail&&i-q[head]+1>k)head++;
		while(head<=tail&&a[q[tail]]>=a[i])tail--;
		q[++tail]=i;
		if(i>=k)cout<<a[q[head]]<<' ';
	}
	cout<<'\n';
	head=1,tail=0;
	for(int i=1;i<=n;i++){
		while(head<=tail&&i-q[head]+1>k)head++;
		while(head<=tail&&a[q[tail]]<=a[i])tail--;
		q[++tail]=i;
		if(i>=k)cout<<a[q[head]]<<' ';
	}
	return 0;
}