solution

肥肠经典的极值问题，可以使用ST表（复杂度为）或者单调队列(复杂度)来做，这里讲一下复杂度更优的单调队列做法。

题目要求长度为k的区间极值，我们从左往右扫并且维护一个队列，队列里存放的为数字下标，并且这个队列要满足两个条件。

条件一：队列中所有位置与当前扫到的位置i之间的距离不超过k。
条件二：队列中下标对应的位置和下标均为有序的。

这样每当我们从i枚举到了i+1，我们都从队首找到与距离大于k的下标弹出去。这样就保证了条件一。

然后考虑维护条件二，我们向队列中添加元素时，需要保证这个元素所添加到的位置前的数字均大于（求最小值是为小于）当前位置的数字。那么我们考虑队尾的数字j，如果现在要添加的位置为i，那么当时，后面的位置肯定是比更优。所以直接将j踢出去即可。

然后就做完了。复杂度

code

/*
* @Author: wxyww
* @Date: 2020-04-02 14:27:21
* @Last Modified time: 2020-04-02 14:31:39
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[N],q[N],T,H;
int main() {
    int n = read(),K = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    H = 1;
    for(int i = 1;i <= n;++i) {
        while(H <= T && q[H] <= i - K) ++H;
        while(H <= T && a[q[T]] > a[i]) --T;
        q[++T] = i;
        if(i >= K) printf("%d ",a[q[H]]);
    }
    puts("");
    H = 1;T = 0;

    for(int i = 1;i <= n;++i) {
        while(H <= T && q[H] <= i - K) ++ H;
        while(H <= T && a[q[T]] < a[i]) --T;
        q[++T] = i;
        if(i >= K) printf("%d ",a[q[H]]);
    }

    return 0;
}