AcWing 154. 滑动窗口
原题链接
简单
作者:
从前
,
2021-05-15 09:49:16
,
所有人可见
,
阅读 154
之所以用两个数组,是通过记录下标的q[]数组来间接控制队列,
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
//q[]里存的是下标,a[]里存的是数据
int q[N], a[N];
int main() {
int n, k;
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++;
//进行单调处理
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;//把下标存进去;
//只有当下标i > k - 1时,才能输出队头;
if(i >= k - 1) 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) printf("%d ", a[q[hh]]);
}
return 0;
}