用模拟队列来维护窗口。
模拟队列:数组。
滑动窗口队列中的元素其实是数组下标!!!
我们需要两个数组,一个是原始数组,用来存储数据的值,另一个是用来模拟队列,存储的是原始数组的下标。
核心代码:
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]]);
}
先用下标 hh
和 tt
判断一下队列数组是否空。
然后用 i - k + 1
计算下标范围。因为 i
是当前的下标,k
是窗口的长度,就是从 i
往前数 k
个,看一下窗口左端点的下标可以到几,然后然后比较一下是否 q[hh]
已经离开窗口了。
检查完左端点之后,再看右端点:有端点我们需要保留最最小的那个数,所以我们用 while
因为可能需要弹出多次。每次都用下标为 q[tt]
的元素和下标为 i
的元素进行大小比较,如果下标 i
更小就把原来的队尾弹出。
然后把 i
加上。
输出之前还需要判定一下是否已经进入了窗口。如果 i
太小还是不用输出。输出的是对头,因为对头既然能够被保存下来,说明一定是足够大或者足够小到被输出的。
难点:注意下标 i
和数组 q[]
存储的下标其实是一个东西。