【每日一题】滑动窗口

原题链接：

https://ac.nowcoder.com/acm/problem/50528

题目大意：

给一个长度为的数组，一个长为的滑动窗体从最左端移至最右端，你只能看到窗口中的个数，每次窗体向右移动一位，如下图：

你的任务是找出窗体在各个位置时的最大值和最小值。

解题思路：

爆内存，线段树只过90%，所以要用单调队列。
本题我们模拟一个单调队列，队列中只存后面可能有用的数据，以取区间最大值为例，如果在一个长度为的区间且，那么知道可以删除掉，这样不会影响区间最大值。所以我们在向队列中增加新元素的时候，我们比较队尾与新元素的大小，如果队尾元素小于新元素，那么队尾元素在后续不会出现了，也就是说被新元素覆盖了，那么就可以删除它，直到无法在覆盖。所以，按照这种消法队首元素一直都是最大的，所以每一次输出就输出队首元素。当然要记得队首元素超出要求的区间时，要删掉该元素。所以单调队列中存取的可以是对应元素在数组的坐标。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(i=a;i<=b;i++)
#define debug(a) cout<<#a<<":"<<a<<endl;
const int INF=1e9+7;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n,m;
int arr[N];
int du[N];

int main(){
    int l,r;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",arr+i);
    }
    du[1]=1;
    l=1,r=2;
    if(m==1){
        cout<<du[l]<<" ";
    }
    for(int i=2;i<=n;i++){
        if(i-du[l]==m){
            l++;
        }
        while(r!=l&&arr[i]<=arr[du[r-1]]){
            r--;
        }
        du[r]=i; 
        r++;
        if(i>=m)
            cout<<arr[du[l]]<<" ";
    }
    cout<<endl;

    l=1,r=2;
    if(m==1){
        cout<<du[l]<<" ";
    }
    for(int i=2;i<=n;i++){
        if(i-du[l]==m){
            l++;
        }
        while(r!=l&&arr[i]>=arr[du[r-1]]){
            r--;
        }
        du[r]=i; 
        r++;
        if(i>=m)
            cout<<arr[du[l]]<<" ";
    }
    cout<<endl;
    return 0;
}