acwing的第157题----滑动窗口

之所以接触到这个单调队列，是在接触多重背包究极版的时候看到的，那道题给的数据从容量从V=1000变成了V=10000，给的物品数据也相应从2000变成了20000，多了10倍，如果只进行二进制优化而不进行单调队列优化的话就会TLE
这时不得不刷一下单调队列的==经典入门题----滑动窗口==
其实老早在OI就见过这道题，不过当时是寒假，就没心思去弄懂它
(其实根本原因是档次不够hhh

现在看看这道题目，其实就是很简单地==在一个长度给定的窗口里面不断地判断你的下一个元素要不要放进去==
放进去的话，单调队列数组存入这个新元素，同时记录下标
接着就是边框的移动和元素的输出这两个微操作了
==废话不多说！！！上代码==

//我一共敲了两遍，全是干货，很硬核
//第二篇也许更详细一点
//总之先把模板背下来吧，不太理解的话先继续往前走，
//等哪天突然通了的话再回过头来复习就好了


#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int n,k;
int q[N];//队列
int p[N];//记录下标的数组
int a[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int head=1,tail=0;
    //先输出滑动窗口的最小值
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[tail]>=a[i])--tail;
        q[++tail]=a[i];//入队
        p[tail]=i;//用这个下标数组记录tail在原序列中的位置
        while(i-p[head]>=k)head++;//当你大于边框的时候就把整个右移
        if(i>=k)printf("%d ",q[head]);
    }
    puts("");
    //第二步输出滑动窗口的最大值
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[tail]<=a[i])--tail;
        q[++tail]=a[i];
        p[tail]=i;
        while(i-p[head]>=k)head++;
        if(i>=k)printf("%d ",q[head]);
    }
}

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000010;
int q[N];//这个数组就是记录以k为大小的框(单调队列)
int p[N];//这个数组用来记录数组下标
int a[N];//存储要处理的元素
int n,k,head,tail;//n是个数，k是框的大小，head是头节点，tail是尾节点
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    //现在处理min单调队列
    head=1,tail=0;//如果你是0~n-1存储进a数组的话就用head=0,tail=-1
    for(int i=1;i<=n;i++){//我要把判断这个元素是放进去好还是不放进去好这个操作重复n次
        while(head<=tail&&q[tail]>=a[i])tail--;//如果这个单调队列里面还有元素而且尾元素比a[i]还要大的话
        tail++;                                //说明若不把这个尾删掉,比尾更小的a[i]就不能排在前面(因为输出的时候总是输出q[head])
        q[tail]=a[i];//上面那个while已经将判断步骤搞定了,现在把a[i]放进单调队列的尾(让a[i]成为单调队列的尾)
        p[tail]=i;//记录单调队列元素的下标(其实就是记录你已经进行到哪一步了)
        while(i-p[head]>=k)head++;//如果现在进行的步骤与头的距离超过了边框的大小,头就向右移动
        if(i>=k)printf("%d ",q[head]);//输出
    }
    puts("");
    //现在处理max单调队列，反过来就好了
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[tail]<=a[i])tail--;
        tail++;
        q[tail]=a[i];
        p[tail]=i;
        while(i-p[head]>=k)head++;
        if(i>=k)printf("%d ",q[head]);    
    }
}

这还有个在csdn里写的版本(其实一毛一样hhh)，有兴趣可以去看看
我的代码注释很详细，其实这也就是板子题啦，熟练了才能灵活的运用到复杂的题目中进行优化，每天想心上人的时候爬起来多敲几遍就好啦