尺取法 学习笔记
尺取法 学习笔记
算法简介
尺取法，简单来说是一种利用［双指针法］遍历满足条件的［区间］的算法。
其算法思想为：对数组保存⼀对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。
尺取法不会去枚举到一定不满足条件的区间，所以是一种［⾼效的枚举区间的⽅法］。
朴素算法
先考虑朴素算法：
- 暴力 \(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\) 增加一直至不满足条件（或未超出限制）；
- \(\Rarr (2) \texttt{ } \operatorname{if} \not \operatorname{end}.\)
参考资料
- https://www.jianshu.com/p/252b8c20f91c
- https://blog.csdn.net/Zhengyangxinn/article/details/104657145
- https://www.luogu.com.cn/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie
- https://www.luogu.com.cn/blog/kkkZzBin0160ZSHS/chi-qu-fa
- https://www.luogu.com.cn/blog/SingerCoder/dp-chi-qu-fa
- https://www.luogu.com.cn/blog/3334SLTH/chi-qu-fa
- https://www.luogu.com.cn/blog/Lucasmjx/chi-qu-fa