滑动窗口

思路分析

暴力做法

对每一个窗口遍历一次，找出最大值与最小值，时间复杂度是$O(nk)$的

单调队列

求最小值和最大值得流程是一样的，我们以最小值为例分析

这里有点像单调栈，不过单调栈是没有限制栈内元素位置的，这里限制了队列元素的下标必须在一个区间范围内

同样我们可以发现性质，如单调栈，如果一个元素在另一个元素的后边，并且值更小，那么对后面的元素寻找区间内最小值的时候，它就是更优解（这里默认都在区间范围内）

最终，我们队列中存储的元素下标对应回去的值，应该是依次递增的。如果不是递增，就会不满足上述性质，因为多出了一些无用信息
每个窗口的最小值也就是队头元素

如同单调队列，我们还是从前往后列举每一个元素

数据存储

队列里存储的是元素在数组中的下标

流程如下

1. 判断队头是否出窗口

当前列举到的元素下标为$i$, 则窗口内第一个元素的下标为$i - k + 1$，将它与队列前端存储的下标对比，若大于队列头，则要进行出队操作

2. 入队

这里要判断当前元素与队尾元素的大小关系来满足单调性，找最小值时候，若当前元素小于等于队尾元素，队尾元素要不断的删除。这样来维持队列单调性

最后该元素入队

3. 输出答案，也就是队头

队列存储的是元素的下标，所以答案应该是$a[q[hh]$

这里，如果枚举的元素下标$< k - 1$，那么是不存在滑动窗口的，此时不输出答案

代码

#include <iostream>

using namespace std;

const int N = 1000010;

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

    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;  //入队

        if (i >= k - 1) printf("%d ", a[q[hh]]);  //如果窗口存在，则输出答案
    }

    puts("");

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

    puts("");

    return 0;
}