尺取法 学习笔记

尺取法 学习笔记

算法简介

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

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

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

朴素算法

先考虑朴素算法:

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

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

尺取法

适用情况

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

使用限制

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

时间复杂度

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

实现细节

  1. 申请两个指针 \(l\)\(r\),表示考虑区间 \([l, r]\) 的结果;
  2. 固定 \(l\),使 \(r\) 不断递增直至满足条件(或超出限制);
  3. 在满足条件(或最后一个未超出限制)的位置更新答案;
  4. 保持 \(r\) 不变,使 \(l\) 增加一直至不满足条件(或未超出限制);
  5. \(\Rarr (2) \texttt{ } \operatorname{if} \not \operatorname{end}.\)

参考资料

热门相关:亿万盛宠只为你   名门盛婚:首席,别来无恙!   魔神狂后   重生之女将星   网游三国之城市攻略