The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

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

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

题目描述

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

解题思路

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

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