用模拟队列来维护窗口。

模拟队列:数组。

滑动窗口队列中的元素其实是数组下标!!!

我们需要两个数组,一个是原始数组,用来存储数据的值,另一个是用来模拟队列,存储的是原始数组的下标。

核心代码:

    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]]);
    }

先用下标 hhtt判断一下队列数组是否空。

然后用 i - k + 1计算下标范围。因为 i是当前的下标,k是窗口的长度,就是从 i往前数 k个,看一下窗口左端点的下标可以到几,然后然后比较一下是否 q[hh]已经离开窗口了。

检查完左端点之后,再看右端点:有端点我们需要保留最最小的那个数,所以我们用 while因为可能需要弹出多次。每次都用下标为 q[tt]的元素和下标为 i的元素进行大小比较,如果下标 i更小就把原来的队尾弹出。

然后把 i加上。

输出之前还需要判定一下是否已经进入了窗口。如果 i太小还是不用输出。输出的是对头,因为对头既然能够被保存下来,说明一定是足够大或者足够小到被输出的。

难点:注意下标 i和数组 q[]存储的下标其实是一个东西。

最后修改:2025 年 04 月 03 日
如果觉得我的文章对你有用,请随意赞赏