单调队列定义:
其实单调队列就是一种队列内的元素有单调性(单调递增或者单调递减)
的队列,答案(也就是最优解)就存在队首,而队尾则是最后进队的元素。因为其单调性所以经常会被用来维护区间最值
或者 降低DP的维数
已达到降维来减少空间及时间的目的。
单调队列可以有两个操作:
1、插入一个新的元素,该元素从队尾开始向队首进行搜索,找到合适的位置插入之,如果该位置原本有元素,则替换它。
2、在过程中从队首删除不符合当前要求的元素。
单调队列实现起来可简单,可复杂。简单的一个数组,一个head,一个tail指针就搞定。复杂的用双向链表实现。
单调队列的一般应用:
1.维护区间最值
2.优化DP