单调队列及 dp 优化
单调队列
-
定义及性质
满足队内元素值单调递增或递减、元素下标单调递增或递减的一个队列,统称为单调队列
-
实现
假如要在队尾新插入一个元素,为了维护单调性,需将不断删除队尾元素,直到插入后满足单调性再插入,关键在于这样做为何是对的。
这里描述值单调递增、下标单调递减的单调队列。
其实就是利用了决策单调性,若满足
a_i\le a_j 且i>j ,则选i 一定优于选j 。从元素值来看,若有区间
[l,r] 包括了a_i,a_j ,那么要取也一定取a_i 而不是a_j ;从下标来看,显然不存在区间[l,r],r\ge i 使得其取不到a_i 却可以取到a_j 。而对于区间[l,r],r<i ,那么自然不会用a_i 淘汰掉a_j 。因此正确性得证。所以单调队列可用于求静态区间最大最小值,且由于每个
a_i 会且仅会被入队、出队一次,所以时间复杂度是线性的。咕咕咕~