【学习笔记】单调队列

public_sickle / 2024-01-27 / 原文

单调队列其实是一个双端队列，可以从队首和队尾出队，但是只能在队尾入队。队列中的元素关系具有单调性。对于维护好的单调队列，队内元素是有序的，取出最大最小值的复杂度是 $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;
}