POJ 2823 Sliding Window 【单调队列】

题目大意：给出一组数，一个固定大小的窗体在这个数组上滑动，要求出每次滑动该窗体内的最大值和最小值。

这就是典型的单调队列，单调队列的作用就在此。单调队列的队首为区间内的最值，可是整个队列不用保持单调。

用两个队列分别处理最大值和最小值，在此说明一下最大值；

往队列中加入值num时，从队尾開始扫，直到遇到一个小于num的d值，将num插入d的后一位。之后的元素所有无效化（无论后面的元素即可）。查找最大值的时候，从队首開始找，假设该元素没在此时的区间的话，查找下一个，直到找到满足条件的第一个元素，这个元素便是最值。

求最小值和最大值大同小异，仅仅须要将加入值num的条件改一下就可以。

代码例如以下：

#include <iostream>
#include <cstdio>
#define N 1000001
using namespace std;

struct que
{
    int i,x;
}q1[N],q2[N];//队列
int a[N];//输入数据
int n,k；
int head,tail;//分别代表队首和队尾的下标，head之前和tail之后的元素都无效
void getmax()
{
    head=1;tail=0;
    for(int i=0;i<n;i++)
    {
        while(head<=tail&&q1[tail].x<a[i])	//检測从队尾開始扫，直到遇到一个小于num的d值
            tail--;
        tail++;				//将num插入d的后一位。</span>
        q1[tail].x=a[i];
        q1[tail].i=i;
        if(i>=k-1)
        {
            while(q1[head].i<=i-k)
                head++;
            if(i!=n-1)
                printf("%d ",q1[head].x);
            else
                printf("%d
",q1[head].x);
        }
    }
}
void getmin()
{
    head=1;tail=0;
    for(int i=0;i<n;i++)
    {
        while(head<=tail&&q2[tail].x>a[i])
            tail--;
        tail++;
        q2[tail].x=a[i];
        q2[tail].i=i;
        if(i>=k-1)
        {
            while(q2[head].i<=i-k)
                head++;
            if(i!=n-1)
                printf("%d ",q2[head].x);
            else
                printf("%d
",q2[head].x);
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        getmin();
        getmax();
    }
    return 0;
}

POJ 2823 Sliding Window 【单调队列】

相关推荐