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

STL

单调队列具体来说，就是保证成员满足单调递增递减的队列。在新成员进入时，需要将他的权与队尾成员的权相比较，若将这个成员直接插入时不满足条件了，则将队尾出队，反复循环直至满足要求或队列为空为止。这时再插入便可以保证队列的单调性了。题目要求同时寻找最大值和最小值，则只需开两个单调队列即可。我们要的答案便是每次操作后队首元素的集合。

但要注意窗口可滑动。当窗口左端坐标超过队首时，这个队首不在窗口中。解决方法是在入队时记录该元素的坐标。在每次入队操作后开始从对首连续删除坐标不满足要求的元素，此时的对首才是我们要求的答案。

再注意要用的容器类型。因为要同时对队首和队尾进行操作，本题选择deque。

Code：

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
using namespace std;
struct node
{
    int nu,ind;//分别是权值和坐标
}s;
deque<node>G;//记录最大值用的队列
deque<node>F;//记录最小值用的队列
int n,k,ma[2000000],mi[2000000];
void input(int w,int in)
{
    s.nu=w;
    s.ind=in;
    while(!G.empty() && s.nu>G.back().nu)G.pop_back();//删除不满足要求的队尾
    G.push_back(s);//压入    下面的操作同理
}
void init(int w,int in)
{
    s.nu=w;
    s.ind=in;
    while(!F.empty() && s.nu<F.back().nu)F.pop_back();//同上
    F.push_back(s);
}
void output(int in)
{
    while(G.front().ind<in)G.pop_front();//将窗体以左的队首出队
    while(F.front().ind<in)F.pop_front();//同上
}
int main()
{
    cin>>n>>k;
    int i,w;
    For(i,1,k)//先进入第一个窗体
    {
        cin>>w;
        input(w,i);
        init(w,i);
    }
    ma[1]=G.front().nu;
    mi[1]=F.front().nu;
    For(i,k+1,n)//滑动处理
    {
        cin>>w;
        input(w,i);
        init(w,i);
        output(i-k+1);
        ma[i-k+1]=G.front().nu;
        mi[i-k+1]=F.front().nu;
    }
    For(i,1,n-k+1)printf("%d ",mi[i]);putchar('\n');//输出
    For(i,1,n-k+1)printf("%d ",ma[i]);putchar('\n');
    return 0;
}