首页 > 代码库 > 小结:单调栈 & 单调队列

小结:单调栈 & 单调队列

概要:

对于维护信息具有单调性的性质或者问题可以转化为具有单调性质的模型的题,我们可以考虑用单调栈或单调队列。

技巧及注意:

技巧很多,只要能将问题转化为单调性问题,就好解决了。

当维护固定长度的单调区间,我们考虑用单调队列,如【BZOJ】3314: [Usaco2013 Nov]Crowded Cows(单调队列)

单调栈维护长度时要进行及时更新,例如:【BZOJ】3039: 玉蟾宫(DP/单调栈)

假设完美状态后再进行减法原理,例如:【BZOJ】1628 && 1683: [Usaco2007 Demo]City skyline 城市地平线(单调栈)

然后是在维护信息的一些技巧,【BZOJ】1657: [Usaco2006 Mar]Mooo 奶牛的歌声(单调栈)

小结:单调栈 & 单调队列