单调队列,顾名思义就是具有单调性的队列O(∩_∩)O~,一般的队列只能从队尾入队、队首出队;为了保持单调队列的单调性,单调队列除具有这两种性质外,还可以从队尾出队。
以单增的单调队列为例,当元素t要入队时,先要从队尾依次弹出所有>=t的元素,再将t加在队尾。
举个例子,如果序列:1 3 -1 -3 10要构成单调队列,
先将元素“1”放入队列中,以初始化队列,
接着元素“3”要入队,队尾元素“1”比“3”小,因此“3”可以直接入队,队列变为1 3,
接着“-1”要入队,从队尾依次弹出元素“3”“1”后将“-1”入队,队列变为-1,
同理“-3”入队后,队列变为-3,
“10”入队后,队列变为-3 10
单调队列有什么用呢?看一道例题:(poj2823)
给定含有n个元素的无序序列a[],和一个整数k,要求求出a[]中每连续k个元素组成的序列中的最小值(或最大值),这样的值可能有1个或n-k+1个。
比较简单的方式,是每次都将k个数排序后输出最值,具有O(N^2logN)的时间复杂度。但如果用单调队列的话,我们可以在O(N)的时间内求解,原因是每个元素最多入队一次、出队一次。
要解决该题,我们还要记录每个元素在原序列中的位置p,每次只需从队首开始找到跟当前元素a[i]距离不大于k的元素(即是i-p+1<=k)输出即可。
以下是zoj2823的部分代码,只写出了最小值的情况,最大值大的家自己想吧。
#include<stdio.h>
#include<stdlib.h>
#define LEN 1000010
typedef struct
{
int p;//记录元素在原序列中的位置
int num;//记录该元素的值
}SQ;
SQ q1[LEN];
int a[LEN];
int f, r;
int n, k;
void InQueue1(int i)
{
while(q1[--r].num >= a[i] && r >= f);
q1[++r].p = i;
q1[r].num = a[i];
r++;
}
int main()
{
int i, j;
int gard;
scanf("%d%d", &n, &k);
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
gard = 0;
q1[1].p = 1;//初始化队列,首元素入队
q1[1].num = a[1];
r = 2;
f = 1;
for(i = 2; i <= k - 1 && i <= n; i++)//k有可能大于n
InQueue1(i);
if(k == 1)//如果k == 1,第一个元素也要输出
{
gard++;
printf("%d", q1[f].num);
}
for(; i <= n; i++)
{
InQueue1(i);
while(i - q1[f].p + 1 > k)//确定队首元素
f++;
if(gard++ == 0)
printf("%d", q1[f].num);
else
printf(" %d", q1[f].num);
}
if(k > n)
printf("%d", q1[1].num);
putchar(10);
//system("pause");
}
posted on 2012-07-19 12:21
小鼠标 阅读(5480)
评论(0) 编辑 收藏 引用 所属分类:
数据结构