AcWing 154. 滑动窗口
原题链接
简单
作者:
Ssenyw
,
2021-09-03 20:57:22
,
所有人可见
,
阅读 239
//单调队列:队首和队伍尾均允许出队,只有队尾可以入队
//队列: 队首出队,队尾入队
/*
使用单调队列就涉及到去头和删尾:
1、队列的头一定是在一段时间前就加入了队列,现在的队列头会不会离开了我们处理的
区间呢?如果它离我们正在处理的i太远了,我们就要把它去掉,去除冗杂的信息。
2、为了保证队列的递减性,在从列队尾新插入元素v时,要考虑队列尾的值是否大于v,如
果是,队列呈现 队列尾-1的值 > 队列尾的值 > v ,此时队列递减性没有消失;如果不是,
队列呈现 队列尾-1的值 > 队列尾的值 < v ,队列递减性被打破。为了维护递减性,
我们做如下考虑:v是最新值,它的位置是目前最靠后的,它可成为以后的最大值,必须
留下;队列尾-1的值与v大小不定,不能冒然删去它;队列尾的值夹在v和队列尾-1之间,
它不但不是最大值,对于以后的情况又不如v优,因为v相比队列尾更靠后(v可以影响到
后m个值,队列尾只能影响到从它的位置往后数m-1个值),而且值更大,所以删队列尾是
必定的。
在维护好一个 区间正确、严格递减 的单调递减队列后,队列头就是当前区间的最大值了。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int q[N],hh=0,tt=-1,a[N];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d", &a[i]);
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i-k+1>=0) printf("%d ",a[q[hh]]);
}
printf("\n");
hh=0,tt=-1; //一定要初始化
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i-k+1>=0) printf("%d ",a[q[hh]]);
}
return 0;
}