AcWing 154. 滑动窗口
原题链接
简单
作者:
晓龙coding
,
2021-08-20 14:10:51
,
所有人可见
,
阅读 158
#include<iostream>
using namespace std;
const int N = 1000010;
//队列q中装的是下标【重点】
int a[N], q[N], hh = 0, tt = -1;
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//求最小值,维护单增队列【重点】
for (int i = 0; i < n; i++) {
//先检查是否滑出队列【重点】【出队和入队的顺序不能调换】
if (i - q[hh] + 1 > k) hh++;
//再插入新元素
while (tt >= hh && a[i] < a[q[tt]]) tt--;
q[++tt] = i;
if (i >= k - 1) cout << a[q[hh]] << " ";
}
cout << endl;
//求最大值,维护单减队列
tt = -1, hh = 0;
for (int i = 0; i < n; i++) {
//先检查是否滑出队列
if (i - q[hh] + 1 > k) hh++;
//再插入新元素
while (tt >= hh && a[i] > a[q[tt]]) tt--;
q[++tt] = i;
if (i >= k - 1) cout << a[q[hh]] << " ";
}
return 0;
}