AcWing 154. 滑动窗口
标签：准备 tps pac https space const style code 插入
https://www.acwing.com/problem/content/156/
#include using namespace std;
const int N = 1000010;
int a[N], q[N];//a是原来的值，q是队列 存的是下标
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i "%d", &a[i]);
int hh = 0, tt = -1; //定义队头和队尾，开始是空的
for (int i = 0; i //i是右端点
//因为每次最多只有一个数字不在窗口内，所以只需要移动一个，也就是用if
//判断队头是否已经滑出了窗口，先判断是不是空的
if (hh 1 > q[hh]) //终点是i，起点是i-k+1 ，如果起点大于q【hh】，说明已经滑出窗口
hh ++ ;//队头加一 ，加以之后，之前的数字就不会再被用到
while (hh = a[i])
tt -- ; //如果准备插入的数字比队尾的小，那么队尾的就没有用了，那么就把队尾的删掉，会一直删除，直到，不满足hh //虽然会删除，但不会改变滑动窗口的长度，因为滑动窗口是根据下标来移动的
//如果准备插入的数字比队尾的大，就不用删除，直接插进去 ，最终会单调递增
q[ ++ tt] = i;//再把当前的数字插进去，放到队尾，如果之前的删除使队列变为空，因为+1，所以会多一个
if (i >= k - 1) printf("%d ", a[q[hh]]);//因为队头一定会是最小的，所以，输出队头
}
puts("");
hh = 0, tt = -1;
for (int i = 0; i ) {
if (hh 1 > q[hh]) hh ++ ;
while (hh ;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
AcWing 154. 滑动窗口
标签：准备 tps pac https space const style code 插入
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11790104.html
评论