尺取法

zsfz张家斌 · 2023-04-29 11:41:09 · 个人记录

概念：

尺取法简单来说是一种利用双指针遍历获取满足条件的区间的算法。其为一种线性算法。记( l , r )为一个序列内以 l 为起点的最短合法区间，如果有 r 随 l 的增大而增大，使用尺取法。具体做法就是不断枚举 l ，同时求出 r ，由于 r 随l增大而增大，所以 r 只有 n 次变化机会，所以时间复杂度为 O( n )。

尺取法需要满足的条件：区间权值大小满足随区间长度单调变化，即区间越长区间权值越小（或越大）。

尺取法的优点： 不会去枚举到一定不满足条件的区间。

算法模板：

for(int l = 1; l <= n; ++l)
{
    while(r < n && sum < s)
    {
        ++r;
        sum += a[r];
    }
    if(sum >= s && r - l + 1 <= n)
    {
        ans = min(ans, r - 1 + 1);
    }
    sum -= a[l];
}

说明： 首先枚举 l ，就是相当于给所有状态按左端点分类，去枚举以 l 为起点的第一个满足条件的区间。确定l后，++r 就相当于剪枝一定不满足条件的区间，在此过程中维护区间和 sum ，当我们发现终于枚举到第一个满足条件的区间时，去统计一下区间长度最小值。sum -= arr[l] 逻辑很关键，它利用了尺取法的单调性，sum减去后，下一轮枚举新的 l ，这样 l 和 r 是以新的 l 为起点的最接近满足条件的区间，这样省得去枚举以新 l 为起点，右端点为 r 之前得一定不满足条件得区间。