概述

数组长度为n， 滑动窗口大小为k的最小值

题解

1 3 -1 -3 5 5 3 6 7

首先把如果不做优化，n*k

每一步进行观察发现，朴素想法。

其实在每一步的滑动窗口中，保留整个范围内的最小值就可以了，无须其他。
然后队列中队头就是当前窗口的最小值，当窗口向右滑动，滑出时，实际上，最小值会抛出。然后就一个新的最小值补入。

但其实能始终保证队列中的元素是一个单调上升的序列

对于单调，往往有很好的性质，极值就在两边. 查找某个值时用二分即可。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int a[N], q[N];

int main() {
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    int hh = 0, tt = -1;  // head, tail;  hh > tt 表示当前队列为空

    for (int i = 0; i < n; i ++) {
        // 队列中存储的是坐标 if 只执行一次
        if (hh <= tt && i - k + 1 > q[hh]) hh ++; // 队列不为空且队首元素出了窗口，则队首加一，i为终点坐标，i-k+1为起点坐标

        while (hh <= tt && a[q[tt]] >= a[i]) tt --; // 如果大于当前值则弹出

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

    return 0;

}