【每日一题题解】3月30日：滑动窗口

读完题第一感是multiset，写完之后提交，内存超出限制。
然后码了个线段树，内存超出限制。
之后去网上搜了相关知识点，才知道这是典型的单调队列题目。
用一个deque维护一个单调增的队列，这样队尾一定是最小值。维护方法如下：
如果新增一个元素，首先和队首进行比较，如果不大于队首，则队首出队，重复这个过程直到队首小于这个元素为止。
然后每次滑动窗口则需检验队尾的角标，不小于 即可。
求最大值的情况同理。
总复杂度
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll dq[1000010],a[1000100];
int main(){
    int n,i,k;
    cin>>n>>k;
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    int l=0,r=0;
    dq[r++]=1;
    for(i=2;i<=n;i++){
        while(r>l&&a[dq[r-1]]>a[i])r--;
        dq[r++]=i;
        while(dq[l]<=i-k&&l<r)l++;
        if(i>=k)printf("%lld ",a[dq[l]]);
    }
    cout<<endl;
    l=0,r=0;
    dq[r++]=1;
    for(i=2;i<=n;i++){
        while(r>l&&a[dq[r-1]]<a[i])r--;
        dq[r++]=i;
        while(dq[l]<=i-k&&l<r)l++;
        if(i>=k)printf("%lld ",a[dq[l]]);
    }


}