尺取法学习笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了尺取法学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基本技巧——尺取法学习笔记

算法简介

尺取法，简单来说是一种利用［双指针法］遍历满足条件的［区间］的算法。

其算法思想为：对数组保存⼀对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。

尺取法不会去枚举到一定不满足条件的区间，所以是一种［⾼效的枚举区间的⽅法］。

朴素算法

先考虑朴素算法：

暴力 \(O(n^2)\)：对于每一个 \(l\) 指针，枚举 \(r\) 指针。
二分 \(O(n \log n)\)：对于每一个 \(l\) 指针，二分 \(r\) 指针。

其中 \(1\) 可以解决［无单调性的问题］；而 \(2\) 需要保证单调性，可以通过大部分的题目；
但是对于部分 \(n \le 10^6\) 的题目，需要［线性复杂度］的算法，就可以考虑［尺取法］。

尺取法

适用情况

⼀般⽤于求取［有⼀定限制的区间］个数或最短的区间问题。

使用限制

所求解的答案在区间内连续；
区间权值大小满足随区间长度单调变化，即区间越长区间权值不递减或不递增；
在通过判断之后，区间的移动有明确的方向。

时间复杂度

常常可以将时间复杂度从 \(O(n^2)\) 或 \(O(n \log n)\) 优化为 \(O(n)\)。

实现细节

申请两个指针 \(l\)、\(r\)，表示考虑区间 \([l, r]\) 的结果；
固定 \(l\)，使 \(r\) 不断递增直至满足条件（或超出限制）；
在满足条件（或最后一个未超出限制）的位置更新答案；
保持 \(r\) 不变，使 \(l\) 增加一直至不满足条件（或未超出限制）；
回到 \((2) \texttt{ } \operatorname{if} \cancel{\text{e}} \text{nd}.\)

Reference

[1] https://www.jianshu.com/p/252b8c20f91c
[2] https://blog.csdn.net/Zhengyangxinn/article/details/104657145
[3] https://www.luogu.com.cn/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie
[4] https://www.luogu.com.cn/blog/kkkZzBin0160ZSHS/chi-qu-fa
[5] https://www.luogu.com.cn/blog/SingerCoder/dp-chi-qu-fa
[6] https://www.luogu.com.cn/blog/3334SLTH/chi-qu-fa
[7] https://www.luogu.com.cn/blog/Lucasmjx/chi-qu-fa文章来源地址https://www.toymoban.com/news/detail-709907.html

到了这里，关于尺取法学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！