单调队列

单调队列其实是一个双端队列，可以从队首和队尾出队，但是只能在队尾入队。队列中的元素关系具有单调性。对于维护好的单调队列，队内元素是有序的，取出最大最小值的复杂度是 \(O(1)\)，每个元素各进队列一次，出队一次，因此复杂度是 \(O(n)\)。单调队列是主要解决滑动窗口类问题的数据结构。

洛谷 : 单调队列模版

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int N=1e6+5;
int a[N],n,k;
deque<int> q1,q2;	//单调队列
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){	//维护最小值
		if(!q1.empty()&&i-q1.front()>=k) q1.pop_front();
		while(!q1.empty()&&a[q1.back()]>a[i]) q1.pop_back();
		q1.push_back(i);
		if(i>=k) cout<<a[q1.front()]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++){	//维护最大值
		if(!q2.empty()&&i-q2.front()>=k) q2.pop_front();
		while(!q2.empty()&&a[q2.back()]<a[i]) q2.pop_back();
		q2.push_back(i);
		if(i>=k) cout<<a[q2.front()]<<" ";
	}
	cout<<endl;
	return 0;
}