牛客：滑动窗口（单调队列）

之前只系统学习过单调栈，以为单调队列和单调栈差不多，就没学。结果做到一道单调队列的题时，发现自己根本写不出来（高估自己了。。。。）

这是牛客每日一题中的，原题链接：https://ac.nowcoder.com/acm/problem/50528

单调队列：不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小\大的元素。

这道题就是单调队列的模板题

直接上代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Size=1000005;
int a[Size],qmax[Size],qmin[Size],savemax[Size],savemin[Size];
int main()
{
    int n,k,cnt=1;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {scanf("%d",&a[i]);}
    int beg=1,top=0;//qmax队列的队首指针和队尾指针
    int st=1,ed=0;//qmin队列的队首指针和队尾指针
    for(int i=1;i<=n;i++)
    {
        while(beg<=top&&a[i]>=a[qmax[top]])
        {top--;}
        qmax[++top]=i;
        while(st<=ed&&a[i]<=a[qmin[ed]])
        {ed--;}
        qmin[++ed]=i;
        if(i>=k)
        {
            while(qmax[beg]<=i-k)beg++;
            while(qmin[st]<=i-k)st++;
            savemax[cnt]=a[qmax[beg]];
            savemin[cnt]=a[qmin[st]];
            cnt++;
        }
    }
    for(int i=1;i<cnt;i++)
    {printf("%d ",savemin[i]);}
    printf("\n");
    for(int i=1;i<cnt;i++)
    {printf("%d ",savemax[i]);}
    printf("\n");
    return 0;
}

123