牛客网-滑动窗口-(单调队列)

链接：https://ac.nowcoder.com/acm/problem/50528
来源：牛客网

题目描述

给一个长度为N(<=1e6)的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下图：

你的任务是找出窗体在各个位置时的最大值和最小值。

输入描述:

第1行：两个整数N和K；
第2行：N个整数，表示数组的N个元素(≤2e9)；

输出描述:

第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；
第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。

示例1

输入

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

输出

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

思路：

区间性问题，首先要有一个l和r指示区间左右两边。

开一个dq数组，存元素的下标，再通过引用原数组获得值去比较，存下标的好处是可以指示出区间长度。

举例取区间最小值的，每遍历一个a[i]，把队列中比它小的弄掉，让当前这个更小的当头，形成单调队列，l始终指示区间范围最小的，队头用r指示。详看代码。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define inf 0x3f3f3f3f ///填充无限小-0x7f

int n,k;
int a[1000086];
int dq[1000086];///用来存储a[i]的下标，数组a通过下标获取值,区间范围[ i-k,i ], i-k<=l<=r<=i

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    int l=0,r=0;
    dq[0]=1;
    r=1;
    for(int i=2;i<=n;i++)
    {
        while(r>l && a[ dq[r-1] ]>a[i])///要找最小值，那么如果队列中的数 比 a[i]大，那就不要了，通过r--弹出后覆盖
            r--;
        dq[r++]=i;
        if(dq[l]<=i-k && l<r)///l始终要保证在[i-k,i]区间里，很多代码都是用while，其实每次l只加一个就够了
            l++;
        if(i>=k)
            printf("%d ",a[ dq[l] ] );
    }
    printf("
");
    l=r=0;
    dq[r++]=1;
    for(int i=2;i<=n;i++)
    {
        while(r>l && a[ dq[r-1] ]<a[i])
            r--;
        dq[r++]=i;
        if(dq[l]<=i-k && l<r)
            l++;
        if(i>=k)
            printf("%d ",a[ dq[l] ] );
    }
    printf("
");
    return 0;
}