每日一题3月30日 滑动窗口 单调队列

今天的题目比较简单~

题意：
有一个数字序列长度为N，现在有一个长度为K的窗口。每次窗口可以查看到序列中连续的K个数字，求窗口在不同位置时候查看的K个数字序列中的最大值和最小值。

类型：
单调队列

思路：
首先可能会考虑线段树，虽然存在频繁的查询，但是10^6的话nlogn应该还是可以碰一碰的，不过好像会MLE？
可以使用单调队列解决。
单调队列是维护一个单调递增（递减、不递增、不递减）的数据结构，主要通过双端队列进行维护。
在本题中，我们以求最小值为例，维护一个单调不减的队列。
假设逐个读入的数字是1 3 -1 -3 5 3 6 。窗口长度K=3
第一次读入1，入队[1].最小值1
第二次读入3，判断3与队尾元素的大小，3>1入队，[1,3].最小值1
第三次读入-1，判断-1与队尾的大小,-1<3，弹出队尾元素,-1<1弹出队尾元素，入队[-1]。最小值-1
第四次读入-3,判断-3与队尾的大小，-3<-1，弹出队尾元素，入队[-3]。最小值-3
...
我们对即将入队的元素做一个优先级的比较，首先若i<j我们说a[i]的优先级低于a[j]。
显然我们有i<j,a[i]>a[j]的时候，我们不需要维护a[i]；
当i<j,a[i]<a[j]的时候，a[i]如果还在窗口中，那么还是最小值。但是a[j]要入队，因为当a[i]离开窗口时，a[j]就是接下来的最小值了。

那么单调队列的基本过程就得到了：每读入一个数x,判断x与队尾元素的大小，循环弹出小于等于x的队尾元素。接着将x放入队尾。然后循环判断队首元素是否还在范围内，如果不在就弹出队首。上面的过程做完以后，当前的队首元素就是最小值。复杂度为O(n)。
最大值同理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct node{
    int x,idx;
}qu1[maxn*2],qu2[maxn*2];
int ans[maxn];
int main()
{
    int n,k,x,flag=0;
    cin>>n>>k;
    int st1,ed1,st2,ed2;
    st1=ed1=st2=ed2=0;
    int cnt=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);

            while(st1<ed1&&qu1[ed1].x>=x)ed1--;
            qu1[++ed1].x=x;
            qu1[ed1].idx=i;
            while(st1<ed1&&qu1[st1+1].idx+k<=i)st1++;

            while(st2<ed2&&qu2[ed2].x<=x)ed2--;
            qu2[++ed2].x=x;
            qu2[ed2].idx=i;
            while(st2<ed2&&qu2[st2+1].idx+k<=i)st2++;

        if(i>=k){
            printf("%d ",qu1[st1+1].x);
            ans[++cnt]=qu2[st2+1].x;        }
    }
    cout<<endl;
    for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
    cout<<endl;
    return 0;
}