题解：P1886 滑动窗口 /【模板】单调队列

· · 题解

关于单调队列，有一句名言。

如果一个人比你小，还比你强，那你就没救了。

事实上，单调队列确实是这个样子的。

因为当出现一个数比 x 大，还比你晚出现，那代表在包含 x 的区间内，这个数一直比 x 大，而且 x 肯定比这个数先离开区间，那你接下来就不会被输出，不必存储。

单调队列，正是那样，队列里的元素是单调的。

根据上面的说法，容易给出单调队列的写法，我们以维护窗口最大值为例：

  1. 弹出过时的元素；
  2. 当队尾元素 < 新加入的元素时，弹出队尾元素；
  3. 重复操作 2，直到队列为空或队尾元素 > 新加入的元素；
  4. 队首元素就是当前答案；
  5. 移动窗口。

这里根据我们开头的性质，容易得出答案一定正确。

求最小值同理。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,l=1,r=0;
int a[1000005],q[1000005];
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }for(int i=1;i<=n;i++){
        while(l<=r&&a[q[r]]>=a[i]){
            r--;
        }q[++r]=i;
        while(l<=r&&q[l]+k<=i){
            l++;
        }if(i>=k){
            cout<<a[q[l]]<<" ";
        }
    }cout<<"\n";
    l=1,r=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&a[q[r]]<=a[i]){
            r--;
        }q[++r]=i;
        while(l<=r&&q[l]+k<=i){
            l++;
        }if(i>=k){
            cout<<a[q[l]]<<" ";
        }
    }
    return 0;
}

这里不推荐使用双端队列，建议使用手写队列。

注意代码里往队列里插入的是下标而不是元素本身的值。