欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

简单数据结构 之 单调栈&&单调队列

程序员文章站 2024-02-17 10:14:58
...

单调栈我很早就会了,单调队列是刚学的…因为一直没遇到单调队列的题目…
单调栈
建立一个栈,维护这个栈使得栈中元素是有序的,递增or递减
比如说,我们建立一个从栈顶到栈底是递增的栈,然后我们就可以记录出每个数左边第一个大于它的数是多少

void solve(){
    stack<int>sta;
    rep(i,1,5){//当不为空  且左边存在比它小的数
        while(!sta.empty()&&arr[sta.top()]<arr[i]){sta.pop();}
        if(sta.empty()){
            ans[i]=-1;//左边不存在比它大的数
        }else{
            ans[i]=sta.top();
        }
        sta.push(i);
    }
}

注意栈中储存的不是元素值,而是元素下标
单调队列
这个数据结构是用来求区间最值的,比如求出长度为n的数组中 长度为m的连续子序列中最大值是多少
我们需要模拟一个双向队列(用deque的话可能会超时…)

比如说洛谷1886这道模板题

int arr[maxn],ans[maxn],que[maxn];
void output(int n,int k){
    //mn
    int head=1,tail=0;
    rep(i,1,n){
        while(head<=tail&&arr[i]<=arr[que[tail]]){tail--;}
        que[++tail]=i;
        while(que[head]<=i-k){head++;}
        ans[i]=que[head];
    }
    rep(i,k,n-1){
        printf("%d ",arr[ans[i]]);
    }
    printf("%d\n",arr[ans[n]]);

    //mx
    head=1,tail=0;
    rep(i,1,n){
        while(head<=tail&&arr[i]>=arr[que[tail]]){tail--;}
        que[++tail]=i;
        while(que[head]<=i-k){head++;}
        ans[i]=que[head];
    }
    rep(i,k,n-1){
        printf("%d ",arr[ans[i]]);
    }
    printf("%d\n",arr[ans[n]]);
}
void solve(){
    int n=read(),k=read();
    rep(i,1,n){
        arr[i]=read();
    }
    output(n,k);
}
相关标签: 数据结构