单调队列

spoiler posted @ 2011年4月09日 17:10 in 未分类 , 6818 阅读

 

一直弄不明白单调队列是什么,在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。

我们从最简单的问题开始:

给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.

要求:

      f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1

问题的另一种描述就是用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值。

解法一:

很直观的一种解法,那就是从数列的开头,将窗放上去,然后找到这最开始的k个数的最大值,然后窗最后移一个单元,继续找到k个数中的最大值。

这种方法每求一个f(i),都要进行k-1次的比较,复杂度为O(N*k)。

那么有没有更快一点的算法呢?

解法二:

我们知道,上一种算法有一个地方是重复比较了,就是在找当前的f(i)的时候,i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢?当然主要是i的前k-1个数中的最大值了。答案是可以,这就要用到单调递减队列。

单调递减队列是这么一个队列,它的头元素一直是队列当中的最大值,而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素,可以从队列的两端删除元素。

1.首先看插入元素:为了保证队列的递减性,我们在插入元素v的时候,要将队尾的元素和v比较,如果队尾的元素不大于v,则删除队尾的元素,然后继续将新的队尾的元素与v比较,直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了,那么队首的元素什么时候删除呢?由于我们只需要保存i的前k-1个元素中的最大值,所以当队首的元素的索引或下标小于 i-k+1的时候,就说明队首的元素对于求f(i)已经没有意义了,因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时,将队首 元素删除。

从上面的介绍当中,我们知道,单调队列与队列唯一的不同就在于它不仅要保存元素的值,而且要保存元素的索引(当然在实际应用中我们可以只需要保存索引,而通过索引间接找到当前索引的值)。

为了让读者更明白一点,我举个简单的例子。

假设数列为:8,7,12,5,16,9,17,2,4,6.N=10,k=3.

那么我们构造一个长度为3的单调递减队列:

首先,那8和它的索引0放入队列中,我们用(8,0)表示,每一步插入元素时队列中的元素如下:

0:插入8,队列为:(8,0)

1:插入7,队列为:(8,0),(7,1)

2:插入12,队列为:(12,2)

3:插入5,队列为:(12,2),(5,3)

4:插入16,队列为:(16,4)

5:插入9,队列为:(16,4),(9,5)

。。。。依此类推

那么f(i)就是第i步时队列当中的首元素:8,8,12,12,16,16,。。。

Avatar_small
hbq0449 说:
2011年4月09日 18:35

受教了。。。这种算法的核心还是如何有效的保存上一次比较的结果,借以优化下一次比较。

Avatar_small
hello kity 说:
2011年4月10日 15:59

@hbq0449:呵呵 有空多来我博客看看 有问题大家一起 讨教一下

Avatar_small
LostCanvas 说:
2011年4月22日 19:47

(小补充)尾部的元素删掉后不用再考虑,因为将要插入的元素一定优于删掉的元素

Avatar_small
hello kity 说:
2011年4月24日 01:08

@LostCanvas: 没考虑呀 删掉了就不用考虑的

Avatar_small
xh 说:
2012年8月08日 21:04

看了好多博客,就这里讲得最清晰!谢谢了~

Avatar_small
浪子回头 说:
2012年8月23日 01:57

好极了,清晰啊,搜了半天,才搜到这里。。。

Avatar_small
。 说:
2012年8月26日 14:20

索引是怎么一回事? 有什么作用?貌似是个下标性质的,从0开始有方便之处吗?

Avatar_small
alpha 说:
2012年10月12日 14:13

感谢博主,讲得很清晰,最近在看二维单调,看不懂各种囧,看了这篇文章就懂了..

Avatar_small
linux 说:
2013年1月28日 15:32

受教了,写的清楚明白

Avatar_small
DeleteLazy 说:
2013年1月30日 01:41

不错哦,非常好的材料

Avatar_small
hello 说:
2015年7月19日 01:20

非常感谢


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter