AcWing 154. 滑动窗口
原题链接
简单
作者:
chenjiaqiy
,
2023-11-13 17:05:53
,
所有人可见
,
阅读 43
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n,k;
int a[N],q[N]; //q代表单调队列
int main()
{
scanf("%d%d", &n,&k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int hh = 0,tt = -1;
for (int i = 0; i < n; i ++ )
{
//判断队头是否已经弹出队列
if(hh <= tt && i - k + 1 > q[hh]) hh ++; //头出窗口 hh向前移动一格;
while(hh <= tt && a[q[tt]] >= a[i]) tt --; // 若不满足单调性,那么将队尾元素删除;
q[ ++tt] = i; //将元素添加到队尾
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
puts(" ");
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) printf("%d ",a[q[hh]]);
}
puts(" ");
return 0;
}