DP 单调性问题总结罗梓璋单调性：单调性，意思是保持同样的趋向，单调递增或者单调递减
在 DP 中，很多情况下，原来是没有单调性的，但是删去不可能的决策之后，剩下的决策会呈现单调性
具有单调性的决策是有序的，最优决策可能直接在头或者尾 O(1)得到，也可以二分查找 O(logn)得到，总体比 O(n)寻找最有决策的时间要少很多
所以单调性可以解决的问题是：保留可能决策，快速寻找最优决策
单调队列：单调队列的本质是双端队列，单调队列的内部是单调的，新元素从队尾加入，假如新元素加入后不满足单调性，那么令原来队尾的元素出队，直到新元素加入后满足单调性或者队列空了
如单调递减队列原来是 5 2 1，加入一个元素 3，则队列为：5 3
单调队列的开头元素在不满足条件时出队
（另外一种加入元素的可能是，二分查找合适的位置，代替原来的元素，但是不能直接插入元素，在某些题目可能有
例如上面的例子为:5 3 1 或 3 2 1，视具体情况
）单调队列是最简单的处理单调性问题的数据结构，最大的用处是：维护区间最值
维护区间最值的要求是，区间的移动方向固定
（要保证队首不加入元素
）既然区间移动方向固定，那么可以区间每移动一个单位，那么多了一个新的元素，少了一个旧的元素
新的元素一定在最后，旧的元素一定在最前
假如队首的元素已经离开了区间，那么让它出队
我们考虑两个元素 A 和 B，B 比 A 优，而且 B 在 A 的后面，因为 A 比 B 先离开区间，所以有 B 在 A 永远也不可能是最值了
所以新的元素加入队列后，假如队列队尾的元素不如新的元素优，那么就可以删除掉队尾原来的元素，直到队尾的元素比新元素优，才把新的元素加入队尾
我们发现这样的队列和单调队列完全符合，队列中前一个元素一定比后一个优，满足单调性，而且模型也一样
这样区间最值一定是队首的元素，可以 O(1)求出区间最值
能用单调队列
