【每日一题】滑动窗口 (单调队列)

Solution：
经典的单调队列模板题，我们可以用deque来实现。
首先，滑动窗口的size不能大于k，得：r-l<=k；
其次，当每个数进入队列时，若是求最大值，那么队列里比他小的数就不可能再成为答案，得：while(a[r]<=now && r>=0) r--;
分析完毕，上代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,k,a[N],mi[N],ma[N];
deque<int>q1,q2;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(q1.size()&&i-q1.front()>=k)
            q1.pop_front();
        while(q1.size()&&a[q1.back()]>=a[i])
            q1.pop_back();
        while(q2.size()&&i-q2.front()>=k)
            q2.pop_front();
        while(q2.size()&&a[q2.back()]<=a[i])
            q2.pop_back();
        q1.push_back(i);
        q2.push_back(i);
        if(i>=k)
        {
            mi[i]=a[q1.front()];
            ma[i]=a[q2.front()];
        }
    }
    for(int i=k;i<=n;i++)
           cout<<mi[i]<<' ';
    cout<<'\n';
    for(int i=k;i<=n;i++)
           cout<<ma[i]<<' ';
    return 0;
}