博客

单调队列到底是什么呢？

简单地按照字面意思来说，单调队列是一种队列（踢飞）

但是这种队列和普通的队列有着很大的区别，怎么说呢：

它的队首和普通的队列一样，只能删除元素。

而它的队尾既可以添加元素也可以删除元素。

通常来说也可以叫做输入受限的双端队列（栈）。

单调队列是做什么用的呢？

简单来说就是用来维护一段区间内的单调上升/下降性质，导出性质就是也可以用来维护一个区间内的最值。

我们先来看一道例题：

poj 2823

题目大意

给你n个数字和一个长度k，让你从前到后输出每个长度为k的区间内的最小值/最大值。

思路

1.暴力

从前到后每个区间遍历一遍，复杂度是O（n*k），铁定超时了

2.线段树维护区间最值

n的范围是10^6，线段树需要4*10^6的空间貌似不会爆，时间复杂度是O（nlogn），可以接受

但是对这道题而言，单调队列显然是优于线段树的另一种思路，先来了解一下它的

工作原理

假设现在我们维护一个递减（最大值）的单调队列，当一个数据想要入队时，需要执行以下操作：

①从队尾到队首开始遍历，如果碰到元素比待入队元素要小，那么这个元素便失去了作用（因为维护的是最大值，如果有一个比当前值小，那它一定不是最大的），将其出队。直到碰到一个比当前值大的元素，跳出循环；

②从队首开始清除

已经不符合条件的元素


（比如已经“过时”即不在当前区间内的元素，视题目而定）；

在执行①之后，队列中所有之前元素都比当前元素大

执行②之后，队列中不再有“过时”元素，即此时队列中只有在区间内而且队首元素就是最大值。

复杂度

因为每个元素都只会入队一次和出队一次，所以复杂度为O（n）。

然后这道题目就可以成功地套上板子做出来了~~

不知道为什么c++提交就可以过，g++会超时，总之poj上还有好多奇怪的问题。。。。

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define sqr(a) (a)*(a)
#define lan(a,b) memset(a,b,sizeof(a))

using namespace std;

int a[1000010];
int num1[1000010];
int num2[1000010];
int b[1000010];

int c[1000010];
int d[1000010];

int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        lan(a,0);
        lan(b,0);
        lan(c,0);
        lan(d,0);
        lan(num1,0);
        lan(num2,0);
        int h1=0,t1=0;
        int h2=0,t2=0;
        for(int i=1;i<=n;i++)
        {
            int tem;
            scanf("%d",&tem);
            while(h1<t1&&a[t1-1]>tem) t1--;
            a[t1++]=tem;
            num1[t1-1]=i;
            while(i-num1[h1]+1>k) h1++;
            if(i>=k)
                c[i]=a[h1];
            while(h2<t2&&b[t2-1]<tem) t2--;
            b[t2++]=tem;
            num2[t2-1]=i;
            while(i-num2[h2]+1>k) h2++;
            if(i>=k)
                d[i]=b[h2];
        }
        for(int i=k;i<=n;i++)
        {
            if(i==n)
                printf("%d\n",c[i]);
            else
                printf("%d ",c[i]);
        }
         for(int i=k;i<=n;i++)
        {
            if(i==n)
                printf("%d\n",d[i]);
            else
                printf("%d ",d[i]);
        }
    }
    return 0;
}