题目描述

给定一个大小为$n≤106$
的数组。

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

样例

8 3
1 3 -1 -3 5 3 6 7

｀｀｀
-1 -3 -3 -3 3 3
3 3 5 5 6 7
｀｀｀

算法

(单调队列)

1．N要开够，不然会ＳE
2. if(hh <= tt && i - q[hh] + 1 > k)是要保证后面的语句while()和q[++ tt] = i可以合法执行，这句代码保证的是窗口的大小一定是<= k的。只有这种情况下，我们才能 往队列中添加元素。
3. q[++ tt] = i的执行是没有条件判断的，就是怎么说这句都会执行，所以我们要把这种语句放在最后面执行，前面放一些有条件判断的。
4. 当i枚举到，也就是窗口中的元素开始滑过k个元素后，就可以把队头输出，因为队头存储的就是每一次滑动窗口中k个元素的最小值。
5. 我之前有仔细想过while(hh <= tt && a[q[tt]] > a[i])这句代码，因为我们是在存储最小值，每个窗口的最小值都存储在队列q的队头中，当新进来的a[i]比当前队尾元素要小的时候，说明有比当前队尾更合适的元素放进去了，那么就删除当前队尾元素tt --，求最大值同理的。
6. 队列q[N]中，元素个数可以是<= k的，但不会大于k，如果给定的序列是单调上升的，那么求最小值的时候，队列q中的元素就会一直是k个，如果是单调递减的，那么队列中的元素始终都会是1个。可以细细体会下。

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010;   // **1

int hh, tt = -1;
int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && i - q[hh] + 1 > k) hh ++;  // **2
        while(hh <= tt && a[q[tt]] > a[i]) tt --;  // **3
        q[++ tt] = i;                             // **4

        if(i >= k - 1) printf("%d ", a[q[hh]]);   // **5
    }

    cout << endl;

    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && i - q[hh] + 1 > k) hh ++;
        while(hh <= tt && a[q[tt]] < a[i]) tt --;
        q[++ tt] = i;

        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }

    return 0;
}