@xzyxzy
2018-04-01T17:00:20.000000Z
字数 869
阅读 1790
数据结构
单调队列单调栈是很基础的数据结构,常用来优化一些东西比如说优化DP
那么大概意思就是在栈或队列中按照某关键字单调维护信息,从而实现一些功能
其实很久之前接触过单调队列和单调栈,但一直没有刷题,趁这两天被LCT弄晕的时候复习下这些
先看题
例如:滑动窗口
比如求一个滑动区间的最小值,那么维护一个从到单调递增的队列,那么每次滑动从删数,在处加数的时候写while(Q[tail]>=x&&head<=tail)tail++;
意思就是存在在一个数后面还比小的数,那么这区间取肯定会更优,对答案产生不了贡献于是在队列中删掉
这个想了很久,最后别人告诉我用单调栈维护
维护一个自栈底至栈顶递减的单调栈,每次加入一个数,判断while(zhan[top]>=x&&top)top--;
这么做就可以保证zhan[top]<x
找到第一个比小的数了,而且还有利于下次寻找答案
例题:良好的感觉
这类题目经常求最大或最小的什么,就是二分答案的套路了
例如:花盆Flowerpot、好消息,坏消息
哇操看题就好了:[SCOI2010]股票交易,可怕。。
先想出线段树的方法再用单调队列优化掉一个