题意

给定 和数组 。求 中的最大值和最小值 。

分析

这题要用到单调队列。
什么是单调队列？顾名思义，就是里面元素是单调的队列。
假如我们有这么一个队列，里面的元素都是合法且单调的。那么最大值和最小值不是呼之欲出了吗？
那么现在如何维护队列单调呢？
以求最大值为例。
假如当前维护了一个队列。现在新插入一个元素，这个元素如果比上一个元素大，那么上一个元素一定不会作为答案出现在之后的滑动窗口中，因为这个元素不仅在上一个元素的后面，而且还比它大。于是，上一个元素可以滚蛋了！然后再比较它和上上个元素，一直比较下去。比较完，我们得到了就是一个单调减的队列，里面的元素都无法再删去了！那么最大值就是队首的值。
做完了吗？
还没有！滑动窗口的大小是有限制的，也就是说，当目前的 和队首的距离超过 ，我们就要跟队首说拜拜了。队首要加一。这样子，我们就成功维护了一个长度为 且单调减的队列，最大值在队首。
求最小值的过程和最大值几乎一模一样。

代码如下

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int q[N], a[N], x = 1, y;
int main(){
    int i, j, n, m;
    n = read(); m = read();
    for(i = 1; i <= n; i++) a[i] = read();
    for(i = 1; i <= n; i++){
        q[++y] = i;
        while(x < y && a[q[y]] <= a[q[y - 1]]) q[y - 1] = q[y], y--;
        while(x <= y && i - q[x] + 1 > m) x++;
        if(i >= m) printf("%d ", a[q[x]]);
    }
    printf("\n");
    x = 1, y = 0;
    for(i = 1; i <= n; i++){
        q[++y] = i;
        while(x < y && a[q[y]] >= a[q[y - 1]]) q[y - 1] = q[y], y--;
        while(x <= y && i - q[x] + 1 > m) x++;
        if(i >= m) printf("%d ", a[q[x]]);
    }
    return 0;
}