算法基础课题解合集

思路

以下讨论滑动窗口的最小值，最大值请自行推理。

我们可以用和单调栈类似的思路，假设当前输入了 $5$ 和 $8$，接着输入了一个 $2$，那么显然 $5$ 和 $8$ 都不可能是答案，直接删掉就好了。

我们可以用一个特殊的队列来维护此过程，这个队列需要满足在队尾删除的工作（其实就是 $tt –$），里面存放下标，如果新输入的数比某些下标对应的数要小那么就把这些下标删掉，然后我们还需要把距离这个数的距离超过 $m$ 的数给删掉，因为此数已经不可能是答案了，滑动窗口的最小值即是 $hh$ 对应的数（当然每次还得把新输入的数插入进队列里）。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m, a[N];
int q[N], hh, tt = -1;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
        while (hh <= tt && a[q[tt]] >= a[i]) tt --;
        while (hh <= tt && i - q[hh] >= m) hh ++;
        q[++ tt] = i;
        if (i >= m - 1) printf("%d ", a[q[hh]]);
    }
    hh = 0, tt = -1;
    puts("");
    for (int i = 0; i < n; i ++) {
        while (hh <= tt && a[q[tt]] <= a[i]) tt --;
        while (hh <= tt && i - q[hh] >= m) hh ++;
        q[++ tt] = i;
        if (i >= m - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$