登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.1 栈与队列 › 栈与队列 / 搜索
JSON MD

2.1 栈与队列

单调栈 Largest Rectangle in a Histogram
20 行
CPP JSON
【单调栈(Largest Rectangle in a Histogram)】 单调栈的算法实现模板。
C++ 19 行 CPP
#include<algorithm>
#include<cstdio>
int i,n,t,wi,a[100005],Q[100005],W[100005];
long long ans;
int main(){
    while(scanf("%d",&n)!=EOF){
        if(!n)break;
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        ans=a[n+1]=t=0;
        for(i=1;i<=n+1;i++)
            if(a[i]>Q[t])Q[++t]=a[i],W[t]=1;
            else{
                wi=0;
                while(t&&a[i]<=Q[t])ans=std::max(ans,(long long)(wi+=W[t])*Q[t--]);
                Q[++t]=a[i],W[t]=wi+1;
            }
        printf("%lld\n",ans);
    }
}
对顶栈 Editor
29 行
CPP JSON
【对顶栈(Editor)】 对顶栈的算法实现模板。 关键配置: N=1e6+5
C++ 28 行 CPP
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+5;
int m,x,tl,tr,L[N],R[N],f[N],s[N];char a;
int main(){
    while(scanf("%d",&m)!=EOF){
        s[0]=0;f[0]=-0xfffffff;tl=tr=0;
        while(m--){
            cin>>a;
            if(a=='I'){
                scanf("%d",&x);
                L[++tl]=x;
                f[tl]=max(f[tl-1],s[tl]=s[tl-1]+x);
            }
            else if(a=='R'){
                if(tr){
                    x=L[++tl]=R[tr--];
                    f[tl]=max(f[tl-1],s[tl]=s[tl-1]+x);
                }
            }
            else if(a=='Q')scanf("%d",&x),printf("%d\n",f[x]);
            else if(a=='L'){if(tl)R[++tr]=L[tl--];}
            else if(tl)tl--;
        }
    }
}
表达式求值 加 减 乘 除 幂 括号
52 行
CPP JSON
【表达式求值(加 减 乘 除 幂 括号)】 代码包含 mi, pop 等核心函数,实现了 表达式求值 的算法逻辑。 核心函数: LL mi(LL x,LL k) — 核心算法函数 void pop(char fh) — 弹出元素
C++ 51 行 CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define LL long long
using namespace std;
int n,f,t1,t2,i,power[300],ch[40];
LL x,sum[40];string a;
LL mi(LL x,LL k){
    LL s=1;
    while(k){
        if(k&1)s=(s*x);
        x=(x*x);k>>=1;
    }
    return s;
}
inline void pop(char fh){
    t1--;t2--;
    if(fh=='+')sum[t1]+=sum[t1+1];
    if(fh=='-')sum[t1]-=sum[t1+1];
    if(fh=='*')sum[t1]*=sum[t1+1];
    if(fh=='/')sum[t1]/=sum[t1+1];
    if(fh=='^')sum[t1]=mi(sum[t1],sum[t1+1]);
}
int main(){
    cin>>a;a='('+a+')';n=a.size();
    power['(']=0;power['+']=power['-']=1;power['*']=power['/']=2;power['^']=3;
    while(i<n){
        x=0,f=0;
        while(isdigit(a[i]))x=x*10+a[i++]-'0',f=1;
        if(f)sum[++t1]=x;
        if(a[i]=='(')ch[++t2]=a[i++];
        if(a[i]==')'){
            while(ch[t2]!='(')pop(ch[t2]);
            i++;t2--;
        }
        if(power[a[i]]){
            if(a[i]=='-'&&a[i-1]=='('){
                x=0,i++;
                while(isdigit(a[i]))x=x*10+a[i++]-'0';
                sum[++t1]=-x;
            }
            else {
                while(power[a[i]]<=power[ch[t2]])pop(ch[t2]);
                ch[++t2]=a[i++];
            }
        }
    }
    while(t2)pop(ch[t2]);
    printf("%lld",sum[1]);
}
单调队列:蚯蚓 f
42 行
CPP JSON
【单调队列:蚯蚓】 代码包含 f, cmp 等核心函数,实现了 单调队列:蚯蚓 的算法逻辑。 核心函数: int f(无参数) — 核心算法函数 bool cmp(int a,int b) — 核心算法函数 关键配置: N=7100005
C++ 41 行 CPP
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=7100005;
int A[N],B[N],C[N],ans[N],h1,t1,h2,t2,h3,t3,s[100005],tmp,re,x,i,n,m,q,u,v,t;
double p;
inline int f(){
    int a=-0xfffffff;
    if(h1<=t1)a=max(a,A[h1]);
    if(h2<=t2)a=max(a,B[h2]);
    if(h3<=t3)a=max(a,C[h3]);
    if(h1<=t1&&a==A[h1])h1++;
    else if(h2<=t2&&a==B[h2])h2++;
    else h3++;
    return a;
}
inline bool cmp(int a,int b){return a>b;}
int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=1.0*u/v;h1=h2=h3=1;
    for(i=1;i<=n;i++)scanf("%d",&s[i]);
    sort(s+1,s+n+1,cmp);
    for(i=1;i<=n;i++)A[++t1]=s[i];
    for(i=1;i<=m;i++){
        x=f();
        x+=tmp;
        if(i%t==0)printf("%d ",x);
        re=p*x;
        B[++t2]=re-tmp-q;
        C[++t3]=x-re-tmp-q;
        tmp+=q;
    }
    printf("\n");
    for(i=h1;i<=t1;i++)ans[++ans[0]]=A[i];
    for(i=h2;i<=t2;i++)ans[++ans[0]]=B[i];
    for(i=h3;i<=t3;i++)ans[++ans[0]]=C[i];
    sort(ans+1,ans+ans[0]+1,cmp);
    for(i=1;i<=ans[0];i++)
        if(i%t==0)printf("%d ",ans[i]+tmp);
    return 0;
}
滑动窗口 数组维护单调队列
20 行
CPP JSON
【滑动窗口(数组维护单调队列)】 滑动窗口的算法实现模板。 关键配置: N=1e6+5
C++ 19 行 CPP
#include<algorithm>
#include<cstdio>
const int N=1e6+5;
int n,k,i,h,t,a[N],Q[N],D[N];
int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        while(h<=t&&Q[t]>=a[i])t--;Q[++t]=a[i],D[t]=i;
        while(h<t&&D[h]+k-1<i)h++;
        if(i>=k)printf("%d ",Q[h]);
    }
    printf("\n");h=t=0;
    for(i=1;i<=n;i++){
        while(h<=t&&Q[t]<=a[i])t--;Q[++t]=a[i],D[t]=i;
        while(h<t&&D[h]+k-1<i)h++;
        if(i>=k)printf("%d ",Q[h]);
    }
}
黑匣子 优先队列
34 行
CPP JSON
【黑匣子(优先队列)】 黑匣子的算法实现模板。
C++ 33 行 CPP
#include<bits/stdc++.h>
#define itn int
#define mian main
using namespace std;
int len,a[30005],piu,op;
char s;
priority_queue<int,vector<int>, greater<int> >sak;
priority_queue<int,vector<int>,less<int> >b;
int main(){
    while(scanf("%c",&s)){
        if(s=='A'){
            while(s!='(') scanf("%c",&s);
            scanf("%d",&a[++len]);
            getchar();
            piu++;
        }
        if(s=='G'){
            getchar();
            getchar();
			while(op<piu){
            	op++;
           	 	b.push(a[op]);
           	 	sak.push(b.top());
            	b.pop();
        	}
        	printf("%d ",sak.top());
        	b.push(sak.top());
        	sak.pop();
        }
        getchar();
    } 
    return 0;
}
已复制