单调队列,顾名思义就是具有单调性的队列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的部分代码,只写出了最小值的情况,最大值大的家自己想吧。


posted on 2012-07-19 12:21 小鼠标 阅读(5479) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜