单调队列两种实现方法

P1886 滑动窗口 /【模板】单调队列

思路:

用一个数组q[N]来演示队列用一个变量h来指明队头下标,用t来指明队尾下标数组q[N]存储a[N]的元素下标根据条件调整队头和队尾元素出队

#include
using namespace std;
#define N 10000005
int a[N],q[N];
int n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	//求最小值 
	int h=1,t=0;
	for(int i=1;i<=n;i++){
		//窗口大小为k,i为窗口右端点,i-k+1为窗口左端点下标
		//q[h]是此时队列中队头元素的下标,如果此时队头的下标超出窗口左端点,则出队 
		while(t>=h && i-k+1>q[h])
			h++;
		//待入队元素a[i],若队尾元素小于a[i]则出队 
		while(t>=h && a[i]=k)
			cout<=h && i-k+1>q[h])
			h++;
		while(t>=h && a[i]>a[q[t]])
			t--;
		q[++t]=i;
		if(i>=k)
			cout< 
deque双端队列 
原理和上面类似
 
#include
using namespace std;
#define N 1000005
int a[N];
deque q;
int n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	//求最小值
	for(int i=1;i<=n;i++){
		while(!q.empty()&&i-k+1>q.front())
			q.pop_front();
		while(!q.empty()&&a[i]<=a[q.back()])
			q.pop_back();
		q.push_back(i);
		if(i>=k)
			cout<q.front())
			q.pop_front();
		while(!q.empty()&&a[i]>=a[q.back()])
			q.pop_back();
		q.push_back(i);
		if(i>=k)
			cout< 
总结 
虽然两种方法都可以实现单调队列,但是
 在刷题中发现,使用普通数组来模拟单调队列比STL中的deque方法效率更高
 
!!!
 推荐使用:普通数组实现单调队列