单调栈小结
2018-06-17 20:46:04来源:未知 阅读 ()
单调栈
单调栈是解决这样一类问题
给出$n$个数,问每一个数向左第一个比它小的数是谁
如果直接暴力的话,最坏情况下肯定是$O(n^2)$的,但是单调栈可以在$O(n)$的时间内解决这类问题
实现
单调栈,顾明思议嘛,就是维护一个具有单调性的栈,至于是单调递增还是单调递减,这个视题目而定
对于上面那个问题而言,我们需要维护一个单调上升的序列
加入一个元素的时候,若当前元素比栈顶元素小,那么就不断的弹出栈顶元素,直到整个栈满足单调
那么该位置向左第一个比它小的就是栈顶
上面说的太抽象了
比如,我们有一个序列$2,4,3,5,2$
设$ans[i]$表示第$i$个位置的答案
$2$加入序列,此时序列为$2$,$ans[1]=0$
$4$加入序列,此时序列为$2,4$,$ans[2]=2$
$3$加入序列,我们发现,如果将$3$直接加入序列,此时序列将不满足单调性,于是先删除$4$,再加入$3$,此时序列为$2,3$,$ans[3]=2$
$5$加入序列,此时序列为$2,3,5$,$ans[4]=5$
$2$加入序列,删除$2,3,5$,加入$2$,此时序列为$2$,$ans[5]=0$
考虑每一个元素最多被加入/删除一次,因此时间复杂度为$O(n)$
至于为什么,感觉挺显然的吧,就是利用单调性
例题
都是些水题
洛谷P2688
题解
HDU1506
题解
BZOJ1007
有些难度,用到了单调栈的思想
题解
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:6.QT-简易计算器实现(详解)
- 单调队列模板【附例题】 2020-05-05
- 单调队列 2020-02-07
- 单调栈 2020-02-07
- 结题报告 2020-01-12
- 初级线段树小结 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash