【3月30日每日一题】 滑动窗口 Editional
滑动窗口
https://ac.nowcoder.com/acm/problem/50528
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;
} 
查看5道真题和解析