首页 > 代码库 > POJ 2823 Sliding Window 【单调队列】

POJ 2823 Sliding Window 【单调队列】

题目链接:http://poj.org/problem?id=2823

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

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

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

往队列中加入值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\n",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\n",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;
}