NC51001 Sliding Window

原题链接：传送门

思路：这道题是滑动窗口的模板题，解决方法是用一个双端队列维护一个大小为k的窗口，然后我们让这个窗口每次移动一下，在移动的过程中维护窗口的最大值或者最小值（维护的答案就在队列的头部），重点介绍一下如何用双端队列来维护，首先为什么要用双端队列而不用一般的队列呢？因为我们要实现在队头的删除和队尾的删除与插入操作，那么队头删除的是什么？以下拿窗口的最小值为例：队头删除的就是当维护的窗口超过我们要维护的窗口时，就需要删除也就是 if(!q1.empty()&&q1.front()<i-k+1)q1.pop_front();那么我们如何维护窗口头部是最小值呢？当存在我们的尾部比要进来的元素大时，这个时候就需要删除尾部的元素，这样做的目的是让窗口内的最小值走到窗口的头部while(!q1.empty()&&a[i]<a[q1.back()])q1.pop_back();最后当存在我们维护的窗口达到k时，输出数据

#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+5;
int a[N];
void minx(int n,int k)
{
    deque<int>q1;
    for(int i=0;i<n;i++)
    {
        while(!q1.empty()&&a[i]<a[q1.back()])
        q1.pop_back();
        if(!q1.empty()&&q1.front()<i-k+1)
        q1.pop_front();
        q1.push_back(i);
        if(i>=k-1)cout<<a[q1.front()]<<" ";
    }
}
void maxx(int n,int k)
{
    deque<int>q2;
    for(int i=0;i<n;i++)
    {
        while(!q2.empty()&&a[i]>a[q2.back()])
        q2.pop_back();
        if(!q2.empty()&&q2.front()<i-k+1)
        q2.pop_front();
        q2.push_back(i);
        if(i>=k-1)cout<<a[q2.front()]<<" ";
    }
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>a[i];
    minx(n,k);
    cout<<endl;
    maxx(n,k);

    return 0;
}