单调队列

单调队列

定义

• 单调队列，即单调递减或单调递增的队列。
• 不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小（大）的元素。
• 一般用数组直接维护，常用于解决区间最值问题。

实现

以最小值为例。

• 用q[i]表示队列，用head指向队头，用tail指向队尾。

• push

  加入一个元素，从队尾向前遍历，遇到比要加入元素大的就删掉，直到一个不比它大的。

  注意队列不能为空，即head<=tail

  while(head<=tail&&a[i]>a[q[tail]])	tail--;
  q[++tail]=i;
  

• pop

  删除一个不合法元素，从队头向后遍历，遇到超出区间的就删掉，直到一个在区间内的（这也是单调的）。

  while(head<=tail&&q[head]+k<=i)	head++;
  

• top

  经过上面两个操作，取出队列的头元素 ，就是当前区间的极值，即q[head]。

代码

#include<stdio.h>
const int N=1e6+5;
int n,k,a[N];
void min(){
	int q[N]={},head(0),tail=(-1);
	for(int i=0;i<n;i++)
	{
		while(head<=tail&&q[head]+k<=i)	head++;
		while(head<=tail&&a[i]<a[q[tail]])	tail--;
		q[++tail]=i;
		if(i>=k-1)	printf("%d ",a[q[head]]);
	}
	putchar('\n');
	return;
}
void max(){
	int q[N]={},head(0),tail=(-1);
	for(int i=0;i<n;i++)
	{
		while(head<=tail&&q[head]+k<=i)	head++;
		while(head<=tail&&a[i]>a[q[tail]])	tail--;
		q[++tail]=i;
		if(i>=k-1)	printf("%d ",a[q[head]]);
	}
	putchar('\n');
	return;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)	scanf("%d",&a[i]);
	min();max();
	return 0;
}

水题

#include<iostream>

using namespace std;

int n,m;

int q1[1000001],q2[1000001];

int a[1000001];

int min(){

    int h=1,t=0;

    for(int i=1;i<=n;i++)

    {

        while(h<=t&&q1[h]+m<=i) h++;

        while(h<=t&&a[i]<a[q1[t]]) t--;

        q1[++t]=i;

        if(i>=m)cout<<a[q1[h]]<<' ';

    }

    cout<<endl;

}

int max(){

    int h=1,t=0;

    for(int i=1;i<=n;i++)

    {

        while(h<=t&&q2[h]+m<=i) h++;

        while(h<=t&&a[i]>a[q2[t]]) t--;

        q2[++t]=i;

        if(i>=m)cout<<a[q2[h]]<<' ';

    }

}

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>a[i];

    min();

    max();

    return 0;

}include<iostream>

using namespace std;

int n,m;

int q1[1000001],q2[1000001];

int a[1000001];

int min(){

    int h=1,t=0;

    for(int i=1;i<=n;i++)

    {

        while(h<=t&&q1[h]+m<=i) h++;

        while(h<=t&&a[i]<a[q1[t]]) t--;

        q1[++t]=i;

        if(i>=m)cout<<a[q1[h]]<<' ';

    }

    cout<<endl;

}

int max(){

    int h=1,t=0;

    for(int i=1;i<=n;i++)

    {

        while(h<=t&&q2[h]+m<=i) h++;

        while(h<=t&&a[i]>a[q2[t]]) t--;

        q2[++t]=i;

        if(i>=m)cout<<a[q2[h]]<<' ';

    }

}

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>a[i];

    min();

    max();

    return 0;

}

shit