题解 | #滑动窗口#

在做此题时，先是求了，最大值，当窗口中，最右边的数，比窗口内左边的数大的时候，那么左边的数就不可能成为此窗口中，最大的数，因此在此题中，用了两个双端队列deque，一个用来记录最大值，另一个用来记录最小值，在求解最大值的时候，用maxn这个双端队列，记录的是输入数字的下标，第一if语句的判断，i-maxn.front()指的是当前数组中数字的下标i减去队列中，队头的下标是否大于等于滑动窗口的大小。如果满足那么就将队列前的元素弹出。接下来的while循环语句是如果队列不为空，并且当前的数字大于之前的数字那么，就将之前的数字弹出队列，因为，当前的数字比队列中前面的数字大并且在满足滑动窗口的大小，那么之前的数字就不可能成为最大值，故将其弹出。最后只输出以队头为下标的元素。

#include<iostream>
#include<deque>
using namespace std;
deque<int>maxn,minn;
long long n,k,a[1000010];
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(!minn.empty()&&(i-minn.front()>=k))
        {
           minn.pop_front(); 
        }
        while(!minn.empty()&&(a[i] <= a[minn.back()]))
        {
            minn.pop_back();
        }
        minn.push_back(i);
        if(i>=k)printf("%lld ",a[minn.front()]);
    }
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        if(!maxn.empty()&&(i-maxn.front()>=k))
        {
           maxn.pop_front(); 
        }
        while(!maxn.empty()&&(a[i]>=a[maxn.back()]))
        {
            maxn.pop_back();
        }
        maxn.push_back(i);
        if(i>=k)printf("%lld ",a[maxn.front()]);
    }
    return 0;
}