尺取法

尺取法

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

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

阅读更多