尺取法

尺取法

尺取法,又称滑动窗口或双指针,是一种在序列上寻找最优解的方法.对于序列的每个左端点 $l$,让右端点 $r$ 尽可能延伸至最远,得到一个答案区间,$r$ 已到达最远后将与 $l$ 有关的信息弹出,对于多个答案区间找出最优解.复杂度通常为线性.

不过一些时候这样不能保证求得的是最优解,这时就需要其他思路,或者使用莫队(根号算法)暴力求解.

阅读更多
单调队列

单调队列

单调队列是一种特殊维护的队列。一般地,当一新值准备入队时,须先从后向前,将对后来答案没有了影响的点弹出,再从前向后,将所有超出了统计范围的点弹出。对于大多数问题,求解过程中会锁定很多答案区间,在线求最值。

阅读更多