重温单调栈和单调队列

只是人生海海,不知何时能再相见.

单调栈和单调队列是非常基础的数据结构了吧,可以和很多东西结合,比如优化个dp什么的.

这里个人认为单调队列的叫法其实不太对,因为放元素的时候很多元素还是要用队尾出,只不过为了满足某些条件需要在队头pop_front一些元素,更合适的叫法应该叫 单调双端队列吧.

单调栈可以做的事

对于某个元素$i $:

  • 确定左/右边区间第一个比它小/大的数
  • 确定以该元素为最值的最长区间
  • 确定这个元素是否为区间最值
  • 确定以该元素为最值的最长区间

单调双端队列可以做的事

  • 可以查询区间最值
  • 可以优化dp

poj2559

寻找最大子矩形

单调栈

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e5+10;
ll a[maxv];
int st[maxv];
int l[maxv],r[maxv];

int p;
int n;


int main(){
	while(~scanf("%d",&n)){
		if(n==0) break;
		inc(i,1,n) scanf("%lld",a+i);
		p=0;
		inc(i,1,n){
			ll now=a[i];
			while(p>0 && a[st[p-1]]>=now) p--;
			if(p==0) l[i]=1;
			else l[i]=st[p-1]+1;
			st[p++]=i;
		}

		p=0;
		dec(i,n,1){
			ll now=a[i];
			while(p>0 && a[st[p-1]]>=now) p--;
			if(p==0) r[i]=n;
			else r[i]=st[p-1]-1;
			st[p++]=i;
		}

		/*
		inc(i,1,n) cout<<l[i]<<" ";cout<<endl;
		inc(i,1,n) cout<<r[i]<<" ";cout<<endl;
		*/

		ll res=0;
		for(int i=1;i<=n;i++){
			ll t=(r[i]-l[i]+1)*a[i];
			res=max(res,t);
		}
		cout<<res<<"\n";
	}
	return 0;
}

poj2823

寻找长度为k的区间的最值

单调双端队列

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int maxv=1e6+10;
int a[maxv];
int n,k;

int st[maxv],s,t;
int Min[maxv],Max[maxv];


int main(){
	while(~scanf("%d%d",&n,&k)){
		inc(i,1,n) scanf("%d",a+i);

		s=t=0;
		inc(i,1,n){
			int now=a[i];
			while(s<t && a[st[t-1]]>=now) t--;
			st[t++]=i;
			if(i-k+1>=1) Min[i-k+1]=a[st[s]];
			if(st[s]==i-k+1) s++;
		}

		s=t=0;
		inc(i,1,n){
			int now=a[i];
			while(s<t && a[st[t-1]]<=now) t--;
			st[t++]=i;
			if(i-k+1>=1) Max[i-k+1]=a[st[s]];
			while(st[s]<=i-k+1) s++;
		}

		int flag=0;
		inc(i,1,n){
			if(i+k-1>n) break;
			if(flag++) printf(" ");
			printf("%d",Min[i]);
		}
		printf("\n");
		flag=0;
		inc(i,1,n){
			if(i+k-1>n) break;
			if(flag++) printf(" ");
			printf("%d",Max[i]);
		}
		printf("\n");
	}
	return 0;
}

poj2796

单调双端队列

坑点: 如果所有的val都是0

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define ll long long 


int n; const int maxv=1e6+10;
ll val[maxv];
ll st[maxv];
int s,t;
int l[maxv],r[maxv];

ll sum[maxv];

int main(){
	while(~scanf("%d",&n)){
		sum[0]=0;
		inc(i,1,n){
		   	scanf("%lld",val+i);
			sum[i]=val[i]+sum[i-1];
		}

		s=t=0;
		inc(i,1,n){

			ll now=val[i];
			while(s<t && val[st[t-1]]>=now) t--;
			if(s==t) l[i]=1;
			else l[i]=st[t-1]+1;
			st[t++]=i;
		}
		s=t=0;
		dec(i,n,1){
			ll now=val[i];
			while(s<t && val[st[t-1]]>=now) t--;
			if(s==t) r[i]=n;
			else r[i]=st[t-1]-1;
			st[t++]=i;
		}
		ll res=0;
		int tl,tr;

		for(int i=1;i<=n;i++){
			ll t=(sum[r[i]]-sum[l[i]-1])*val[i];

			if(res<t){
				res=t;
				tl=l[i];
				tr=r[i];
			}
		}


		cout<<res<<"\n";
		// 有可能所有的val都是0
		// 那么需要特判
		if(res)
		cout<<tl<<" "<<tr<<"\n";
		else cout<<"1 1\n";
	}
	return 0;

}

poj3250

单调栈

// ac
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

int n;
const int maxv=8e4+10;
int val[maxv];

int st[maxv];
int r[maxv];


int s,t; int main(){
	while(~scanf("%d",&n)){
		inc(i,1,n) scanf("%d",val+i);
		s=t=0;
		dec(i,n,1){
			int now=val[i];
			// 是递减的单调栈
			// 注意如果遇到相同的元素并不需要pop出去
			while(s<t && val[st[t-1]]<now) t--;
			if(s==t) r[i]=n;
			else r[i]=st[t-1]-1;
			st[t++]=i;
		}
		ll res=0;
		inc(i,1,n){
			ll t=r[i]-i;
			res+=t;
		}
		cout<<res<<"\n";
	}
	return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!