文档章节

单调队列

m2012
 m2012
发布于 2012/05/29 14:59
字数 686
阅读 218
收藏 0
简单来说,单调队列是用来解决这样的问题的:
实现一个目标容器buffer,支持3种操作:
不断地向buffer里读入元素、
时不时会去掉当前buffer里的最老的元素
不定期地询问当前buffer里的最小元素。

实现一个buffer,使得上面的操作的代价尽可能小。

而单调队列,是实现该buffer的一个好方法。

为每个读入到buffer的元素封装一个专门的结构体:
struct Element {
    int time;  // 这是该元素被读入buffer时的时间戳,一般从0开始
    int val;    // 该元素的值
};


单调队列,是一个队列,按照从队头到队尾的方向,并且满足2个性质:
(a)元素的time字段依次增加,也就是说,元素是从旧到新的
(b)元素的val字段依次增加,也就是说,元素是从小到大的


我们先考虑一下用普通的队列是怎么实现目标buffer的。
假设Q是一个普通的双向队列,支持push_back, pop_back, push_front, pop_front
然后我们不断地往Q的尾巴push元素。那么:
要插入一个元素的时候,就push_back那个元素。时间为O(1)
要删除最老元素的时候,只需要pop_front。时间为O(1)
要询问当前最小值的时候,就遍历一次队列里的所有元素。时间为O(n)

考虑一下如何改进。
当我们往Q的尾巴插入一个元素x的时候,有一件事我们是可以马上确定的:
插入x前,对于任意y属于Q,如果y.val >= x.val,那么,对于插入x之后的任意一个询问,问题的答案,都绝对不会是y,因为x既比y小,又比y要新。

也就是说,每当我们插入一个最新元素x到Q的尾巴的时候,那些比x大的元素都没有生存价值,因为他们永远不会成为之后的询问的答案,他们存在于这个世界上唯一可以做的事情就是等待某个时候被删除。
既然这样,当我们插入元素x的时候,我们可以从尾巴往头部方向扫描,把那些大于x元素都先pop出来,反正他们永远都不会成为询问的答案。最后,再插入x到尾部。这样子,性质(a)就得到维护了。

当我们需要删除所有在某个时间t之前插入的一些老元素时,只需要从队头往尾巴方向扫描,把插入时间在t之前的元素都pop出来就行了。

© 著作权归作者所有

共有 人打赏支持
上一篇: POJ2373 - 单调队列
下一篇: poj1029 False coin
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
12.8~12.9题解

今天主要写一下题解,总结待整理好后另开一篇发表(大约是明天)。 题面见各大OJ。本次题解都是讨论对于已经列好的DP方程的优化。 【HDU3401】 单调队列优化要求参数分离和枚举区间单调。对于...

myjs999
2017/12/10
0
0
12.9 省选训练总结3(2) DP的优化

目录 数据结构优化 维护前面的DP的最小最大值,使得不需要循环一边去找寻更新值。 滑窗 最重要的一种数据结构优化。维护一个最值单调双端队列,区间单调移动的时候只需要加入维护/弹出元素即...

OwenOwl
2017/12/10
0
0
dp优化 12 - 09

数据结构优化 单调队列优化 其中 双端队列队列,队列内保存之后可能成为最优值的值,保证有单调性。 特点是转移范围有限制。 真·数据结构优化 当 没有单调性时,就可以用线段树之类的数据结...

aziint
2017/12/10
0
0
栈与队列-单调栈,单调队列

什么时候使用? 单调栈 在均摊O(1) 即总时间复杂度为O(n)内实现找到某数右边第一个比它大(小)的数 单调队列 滑窗问题 在运行的过程中能够快速寻求前k个或后k个中最大或最小的值 我们直接来...

weixin_40777696
2017/12/13
0
0
DP优化的三种方法 单调队列优化 斜率优化 决策单调性优化

版权声明:myjs999原创文章 https://blog.csdn.net/myjs999/article/details/83478233 众所周知,DP优化有单调队列优化、斜率优化、矩阵快速幂优化、四边形不等式优化、数据结构优化等。本文...

myjs999
2018/10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何开发一款以太坊(安卓)钱包系列2 - 导入账号及账号管理

这是如何开发一款以太坊(安卓)钱包系列第2篇,如何导入账号。有时用户可能已经有一个账号,这篇文章接来介绍下,如何实现导入用户已经存在的账号。 导入账号预备知识 从用户需求上来讲,导...

Tiny熊
今天
2
0
intellJ IDEA搭建java+selenium自动化环境(maven,selenium,testng)

1.安装jdk1.8; 2.安装intellJ; 3.安装maven; 3.1 如果是单前用户,配置用户环境变量即可,如果是多用户,则需配置系统环境变量,变量名为MAVEN_HOME,赋值D:\Application\maven,往path中...

不最醉不龟归
今天
3
0
聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
2
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
2
0
《万历十五年》的读后感作文4000字

《万历十五年》的读后感作文4000字: 万历十五年,即1587年,距今已过去432年。在明朝276的历史中,这一年很平淡,并没有什么特别之处。黄仁宇的《万历十五年》一书,有别于其他的历史叙述方...

原创小博客
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部