发帖
雷达卡
DP单调性问题总结
罗梓璋单调性：
单调性，意思是保持同样的趋向，单调递增或者单调递减。在
DP中，很多情况下，本来是没有单调性的，但是删去不可能的决策之后，剩下的决策会呈现单调性。具有单调性的决策是有序的，最优决策可能直接在头或者尾
O(1)
得到，也可以二分查找
O(logn)
得到，总体比
O(n)
寻找最有决策的时间要少很多。
所以单调性可以解决的问题是：保留可能决策，快速寻找最优决策。
单调队列：
单调队列的本质是双端队列，单调队列的内部是单调的，新元素从队尾加入，如果新元素加入后不满足单调性，那么令原来队尾的元素出队，直到新元素加入后满足单调性或者队列空了。如单调递减队列原来是
5 2 1
，加入一个元素
3，则队列为：
5 3。单调队列的开头元素在不满足条件时出队。
（另外一种加入元素的可能是，二分查找合适的位置，代替原来的元素，但是不能直接插入元素，在某些题目可能有。例如上面的例子为
:5 3 1
或3 2 1
，视具体情况。）
单调队列是最简单的处理单调性问题的数据结构，最大的用处是：维护区间最值。
维护区间最值的要求是，区间的移动方向固定。
（要保证队首不加入元素。 ...
京公网安备 11010802022788号
