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

单调栈我很早就会了，单调队列是刚学的…因为一直没遇到单调队列的题目…
单调栈
建立一个栈，维护这个栈使得栈中元素是有序的，递增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);
}