【洛谷P1886】滑动窗口

滑动窗口

【题目描述】

有N个数字，以及一个大小为k的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

思路：

k<=N<=1000000,暴力是拿不到全分的，要想解决这个问题，理想的时间复杂度应是O（n），我们可以用一个单调队列维护。

单调队列原理：

　　以维护最大值为例：

　　对于每个新加入区间的值，显而易见的是：对于向右移动的“窗口”，即当前长度为n的区间中，若存在data[q[i]]比data[q[j]]大且q[i]>q[j]（q[i]表示队列中的第i个元素的编号，data[i]表示编号为i的元素的值）,则可以保证q[j]在以后的区间取最大值时是不会产生影响的，我们便可以将q[j]删除，从而得到更加优秀的时间复杂度，所以，当一个新的值入队时，便可以将在其前面入队且值比它小的元素删除。我们便可以发现可以用一个单调队列维护。当然，对于不在当前区间内的“老”元素，要把它从队列中删除。

贴代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,k,a[],queue[],tail,head=,i;

int main()

{

    scanf("%d%d",&n,&k);

    for(i=;i<=n;i++)

    scanf("%d",&a[i]);
　　//最小值 单调递减的队列

    for(i=;i<=k;i++)　　　　//前k个数入队

    {

        while(a[i]<=a[queue[tail]]&&tail>=head)

        tail--;

        queue[++tail]=i;

    }

    for(i=k;i<=n;i++)　　　　//k+1~n依次入队

    {

        while(a[i]<=a[queue[tail]]&&tail>=head)

        tail--;

        queue[++tail]=i;

        if(queue[head]<i-k+) head++;

        printf("%d ",a[queue[head]]);

    }

    puts("");
　　//最大值 单调递增的队列

    memset(queue,,sizeof(queue));

    for(i=;i<=k;i++)

    {

        while(a[i]>=a[queue[tail]]&&tail>=head)

        tail--;

        queue[++tail]=i;

    }

    for(i=k;i<=n;i++)

    {

        while(a[i]>=a[queue[tail]]&&tail>=head)

        tail--;

        queue[++tail]=i;

        if(queue[head]<i-k+) head++;

        printf("%d ",a[queue[head]]);

    }

    return ;

}

巴特西

【洛谷P1886】滑动窗口

最新文章

热门文章