滑动窗口

活动地址：https://ac.nowcoder.com/discuss/394776?type=101&order=0&pos=6&page=2

思路

单调队列的模板题
其实就一个关键地方：拿窗口中最小值为例，假如现在窗口中是1 3 5 6，再下一次滑动来了一个4，那么很明显窗口中的5 6永远不会是最小值，其实单调队列算是一种暴力的优化，就是新来的值可以排除掉一些永远不会是答案的元素，这样就会使得队列呈单调性，每一个窗口的答案总是在最左边。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N,K;
int arr[maxn];
int q1[maxn],q2[maxn],ff1,ff2,tt1 = -1,tt2 = -1;//模拟队列
int mi[maxn],tail1;
int mx[maxn],tail2;
int main(){
    cin>>N>>K;
    for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
    for(int i = 1;i<=N;i++){
        while(ff1 <= tt1 && arr[q1[tt1]] > arr[i]) tt1--; //最小值部分
        q1[++tt1] = i;
        while(q1[ff1]<i-K+1) ff1++; //出队

        while(ff2 <= tt2 && arr[q2[tt2]] < arr[i]) tt2--;//最大值部分
        q2[++tt2] = i;
        while(q2[ff2]<i-K+1) ff2++;

        if(i>=K) mi[tail1++] = arr[q1[ff1]];
        if(i>=K) mx[tail2++] = arr[q2[ff2]];
    }
    for(int i = 0;i<tail1;i++) printf("%d ",mi[i]);puts("");
    for(int i = 0;i<tail2;i++) printf("%d ",mx[i]);

    return 0;
}