AcWing 154. 滑动窗口
原题链接
简单
作者:
花终会凋零
,
2022-04-26 19:49:33
,
所有人可见
,
阅读 156
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int n, k;
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int 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) cout << a[q[hh]] << ' ';
}
cout << endl;
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) cout << a[q[hh]] << ' ';
}
return 0;
}