题目描述

给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。

解题思路

单调队列的经典题目，正如邓老师说的那样，每次区间滑动一个单位,区间内元素从
变为了 可以看出，变化的部分，只有a[l]和a[r+1]，完全没必要把中间部分去遍历很多遍。
这时候就请来了强大的单调队列大大，开辟一个队列，让里面保存的都是可能是答案的下标，并且当前位置的答案下标保存在对头中。
具体的实现过程注释的比较详细，当前元素如果要入队，之前的对头下标如果和自己差距大于m，说明以前的下标不合法了，队头出队。
拿求最小值来说，如果队尾元素大于等于当前a[i]，a[i]入队后，最小值不可能是当前队尾了，队尾元素出队。反复循环直到队尾元素小于a[i]。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e6 + 7;
int a[N], que[N];

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    int l = 0, r = 0; //单调队列队头和队尾
    que[r++] = 1;
    if (m == 1)    printf("%d ", a[1]); //后面从2开始特判下m
    for (int i = 2; i <= n; ++i) {
        //队中存在元素，并且之前的最小元素下标已经不在当前m范围内 出队
        if (r > l && i - que[l] >= m)    ++l;
        //  当前队尾值大于等于a[i] a[i]入队后，最小值一定不会是队尾了，队尾出队
        while (r > l && a[que[r - 1]] >= a[i])    --r;

        que[r++] = i;
        if (i >= m)
            printf("%d ", a[que[l]]); //队头中保存的就是最小值下标位置
    }
    puts("");
    // 最大值类似
    l = r = 0;
    que[r++] = 1;
    if (m == 1)    printf("%d ", a[1]);
    for (int i = 2; i <= n; ++i) {
        //队中存在元素，并且之前的最大元素下标已经不在当前m范围内 出队
        if (r > l && i - que[l] >= m)    ++l;
        //  当前队尾值小于等于a[i] a[i]入队后，最大值一定不会是队尾了，队尾出队
        while (r > l && a[que[r - 1]] <= a[i])    --r;

        que[r++] = i;
        if (i >= m)
            printf("%d ", a[que[l]]); //队头中保存的就是最大值下标位置
    }
    puts("");
    return  0;
}