AcWing 154. 滑动窗口
原题链接
简单
作者:
dsyami
,
2021-05-11 19:19:36
,
所有人可见
,
阅读 264
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int queue[N], hh = 0, tt = -1;
int main()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++ )
{
if(hh <= tt && queue[hh] < i - k + 1) hh ++; //判断左边界(队列头)条件
while(hh <= tt && a[queue[tt]] > a[i]) tt --; //判断队列的单调性
queue[++ tt] = i;
if(i >= k) printf("%d ", a[queue[hh]]); //队头为最小元素的下标
}
puts("");
hh = 0, tt = -1; //再次初始化
for(int i = 1; i <=n; i ++ )
{
if(hh <= tt && queue[hh] < i - k + 1) hh ++;
while(hh <= tt && a[queue[tt]] < a[i]) tt --;
queue[++ tt] = i;
if(i >= k) printf("%d ", a[queue[hh]]);
}
return 0;
}