单调队列

一个支持在队尾插入，队头和队尾删除的队列，整个队列呈单调性

如果要求最大值则维护一个递减的单调队列，最小值则递增

用deque写很方便（前几天用数组模拟队列 代码调不出bug难受死了）

例题 P1886 滑动窗口

思路：

用一个deque，存点的序号（用于判断是否过期）和点的数字。每次新增加一个元素，都要判断

1.前面的点是否过期，过期弹出

2.新加入元素是否比队尾元素的数字大，若大 新加入的元素既时间上比队尾元素更优，数字上也更优，那么弹出队尾元素，一直弹到找到一个比新元素更大的队尾元素或队列为空为止（求最大值的情况）

然后每次输出即可

代码：

#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
struct node{
    int tim,number;
}; 
deque<node> qmin,qmax;
const long long N=1e6+10;
int n,k,a[N],ansmin[N],ansmax[N],cnt=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        while(!qmin.empty()&&qmin.front().tim<(i-k+1)) qmin.pop_front();
        while(!qmax.empty()&&qmax.front().tim<(i-k+1)) qmax.pop_front();
        while(!qmin.empty()&&qmin.back().number>a[i]) qmin.pop_back();
        while(!qmax.empty()&&qmax.back().number<a[i]) qmax.pop_back();
        node h;
        h.number=a[i];
        h.tim=i;
        qmax.push_back(h);
        qmin.push_back(h);
        if(i>=k){
            ansmin[++cnt]=qmin.front().number;
            ansmax[cnt]=qmax.front().number;
        }
    }
    for(int i=1;i<=cnt;i++){
        printf("%d ",ansmin[i]);
    }
    printf("\n");
    for(int i=1;i<=cnt;i++){
        printf("%d ",ansmax[i]);
    }
    return 0;
} 

最近一直在看板子，但感觉学了新东西之后并不能把他们综合运用到一个题上（本来也什么都不会呢=D），可能需要多加练习？还是我脑子太笨了TT