单调队列单调栈
xzyxzy
2018-02-05 11:38:52
#**单调队列单调栈**
Tags:数据结构
##更好阅读体验:https://www.zybuluo.com/xzyxzy/note/1041449
---
##**一、概述**
单调队列单调栈是很基础的数据结构,常用来优化一些东西比如说优化DP
那么大概意思就是在栈或队列中按照某关键字单调维护信息,从而实现一些功能
其实很久之前接触过单调队列和单调栈,但一直没有刷题,趁这两天被LCT弄晕的时候复习下这些
先看题
##**二、题单**
###普及-
- [x] P1886 滑动窗口 https://www.luogu.org/problemnew/show/P1886
- [x] P3088 [USACO13NOV]挤奶牛 https://www.luogu.org/problemnew/show/P3088
- [x] P1714 切蛋糕 https://www.luogu.org/problemnew/show/P1714
- [x] P2216 [HAOI2007]理想的正方形 https://www.luogu.org/problemnew/show/P2216
- [x] P2564 [SCOI2009]生日礼物 https://www.luogu.org/problemnew/show/P2564
###普及
- [x] P3512 [POI2010]PIL-Pilots https://www.luogu.org/problemnew/show/P3512
- [x] P2698 [USACO12MAR]花盆Flowerpot https://www.luogu.org/problemnew/show/P2698
- [x] P2422 良好的感觉 https://www.luogu.org/problemnew/show/P2422
- [x] P2629 好消息,坏消息 https://www.luogu.org/problemnew/show/P2629
- [ ] P2219 [HAOI2007]修筑绿化带
- [ ] P2569 [SCOI2010]股票交易
##**三、做题经验**
###**用处**
####**1、求滑动区间最大/最小值**
例如:[滑动窗口][1]
比如求一个滑动区间的最小值,那么维护一个从$head$到$tail$单调递增的队列,那么每次滑动从$head$删数,在$tail$处加数的时候写```while(Q[tail]>=x&&head<=tail)tail++;```意思就是存在在一个数$A$后面还比$A$小的数$B$,那么这区间取$B$肯定会更优,$A$对答案产生不了贡献于是在队列中删掉
####**2、求某数左边第一个小于它的数**
这个想了很久,最后别人告诉我用单调栈维护
维护一个自栈底至栈顶递减的单调栈,每次加入一个数$x$,判断```while(zhan[top]>=x&&top)top--;```这么做就可以保证```zhan[top]<x```找到第一个比$x$小的数了,而且还有利于下次寻找答案
例题:[良好的感觉][4]
###**套路**
####**1、常与二分答案和前缀和连用**
这类题目经常求最大或最小的什么,就是二分答案的套路了
例如:[花盆Flowerpot][2]、[好消息,坏消息][3]
###**注意事项**
####**1、使用单调队列的时候千万记得时刻head<=tail+1**
###**通法**
**先想出线段树的方法再用单调队列优化掉一个$log$**
[1]: https://www.luogu.org/problemnew/show/P1886//www.luogu.org/problemnew/show/P1886
[2]: https://www.luogu.org/problemnew/show/P2698
[3]: https://www.luogu.org/problemnew/show/P2629
[4]: https://www.luogu.org/problemnew/show/P2422