Question

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

Sample input

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

Sample output

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

Answer:

第一眼看这题好简单啊
直接建立一颗线段树，然后区间查询(easy!)，交上去发现 MLE了40%；😟
考虑更优的解法:
单调队列：就像单调栈一样，保证队列里的下标代表的元素一直是递增或递减。
我们用这个队首维护当前窗口的答案
那么当滑动这个窗口到了Ai时，Ai肯定是要进队列的，那再他进队列之前，就可以把队列里所有比他大的元素(即从队尾开始往前判断)全都出队了(因为这些数字是肯定不会再次对答案造成 贡献了)
然后再将所有不再当前窗口的队首出队。一直维护就是了

这题其实是一道很基础的单调队列模板题，目的应该是为了让大家熟悉一下这种思想。
可以用来优化一些种类的DP。

#include <bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi firse
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+7;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
int n,k,a[maxn],q[maxn];

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&q[l]+k<=i) l++;
        while(l<=r&&a[q[r]]>a[i]) r--;
        q[++r]=i;
        if(i>=k) printf("%d ",a[q[l]]);
    }
    printf("\n");
    l=1;r=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&q[l]+k<=i) l++;
        while(l<=r&&a[q[r]]<a[i]) r--;
        q[++r]=i;
        if(i>=k) printf("%d ",a[q[l]]);
    }
    return 0;
}