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

题目描述

有一个长为

例如：

The array is

输入格式

输入一共有两行，第一行有两个正整数

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例

输入 #1

8 3
1 3 -1 -3 5 3 6 7

输出 #1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

心路历程：

一开始觉得这个题非常简单，看到是什么单调队列的模板，我心想，啥(⊙_⊙)?单调队列？我咋没发现单调？

一开始的想法是从先找到1~k内的最大值和最小值，然后从k+1开始访问，如果当前值比最大值大或者比最大值小，那么就更新这个值，并且把它复制到数组中，最后直接输出结果。

怎么样？思路非常清晰，步骤非常整洁，可惜就是过不去有样例（汗-_-||）

为什么呢?

注意：这里是滑动窗口啊！！滑动！！一开始的最大值和最小值有可能被划出去啊~~

所以上面这种方法肯定行不通，但是厚颜无耻的我还是把偶的非AC代码搬了上来：︿(￣︶￣)︿

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n,k;
ll a[5020000];
ll maxn=-9999999999999,minn=9999999999999; 
ll minnn[5020000],maxnn[5020000];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=k;i++) 
    {
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    maxnn[1]=maxn;
    minnn[1]=minn;
    int mi=1,ma=1;
    for(int i=k+1;i<=n;i++)
    {
        if(a[i]>=maxn) maxn=a[i];
        ma++;
        maxnn[ma]=maxn;
        if(a[i]<=minn) minn=a[i];
        mi++;
        minnn[mi]=minn;
    }
    
    
    for(int i=1;i<=mi;i++) cout<<minnn[i]<<" ";
    cout<<'
';
    for(int i=1;i<=ma;i++) cout<<maxnn[i]<<" ";
    
    return 0;
}

解题思路：

好了，Y(^o^)Y，我们来看一下正解到底是个啥东东

因为这个队列是滑动的，而stl 里面并没有给我们提供滑动类型的队列，所以我们这里需要自己用数组进行模拟

来想一下，假设我原来的数组元素就是样例里的：

1 3 -1 -3 5 3 6 7

设置数组q中保存的是我们当前窗口中最大值的下标

这样的话我们可以发现一个显然的事实：

假设元素为x y z ，那么对于窗口中的最大值来说，如果 y > x ，我们就可以直接把x扔掉啦！因为我们可以用到x的地方只在x之前，而在x之后，始终存在一个y>x ，所以不管怎么样窗口中的最大值一定不是x，那么x还有什么存在的必要吗？没有，所以我们可以直接把它从数组q中删除（从队列中删除）。而入如果x<y，那么x还有可能是整个窗口中的最大值，所以我们保存x。

另外一点需要注意的是，如果当前循环到的元素下标是i ，窗口长度是k ，那么如果 i-k+1 的值（也就是窗口起点的下标）已经大于我们一开始的窗口下标（这里用队列头元素来表示）了，那么我们就必须把队列头元素弹出队列，因为在实际操作中当前元素已经不再这个窗口中了，他已经划出这个窗口了。

并且，按照这样的方式，我们可以直接从头更新队列，而不需要像我一开始的错解一样需要从k+1开始遍历，但是注意一下几点：

1.如果按照我下面的代码来完成单调队列的编写，那么一定要注意数组从0开始存入，存到n-1

2.当我们遍历到的元素下标已经大于k-1的时候就要开始输出啦！！

3.元素头指针初始下标（h）设置为0，尾指针初始下标设置成-1或者0都是可以的，对程序影响不大（反正都可以AC）

(^o^)/~OK，到这，我们终于把所有东西都啰嗦完了(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤

AC代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,k;
int q[5020000],a[5020000];

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int h=0,t=0;
    for(int i=0;i<n;i++)
    {
        while(h<=t&&a[i]<=a[q[t]]) t--;
        t++;
        q[t]=i;
        if(h<=t&&i-k+1>q[h]) h++;
        if(i>=k-1) cout<<a[q[h]]<<" "; 
    }
    
    cout<<'
';
    h=0,t=0;
    for(int i=0;i<n;i++)
    {
        while(h<=t&&a[i]>=a[q[t]]) t--;
        t++;
        q[t]=i;
        if(h<=t&&i-k+1>q[h]) h++;
        if(i>=k-1) cout<<a[q[h]]<<" ";
    }
    
    return 0;
}

----------------------end-----------------------