跳至主要內容

滑动窗口算法

linwu大约 2 分钟

滑动窗口算法

滑动窗口算法是一种常用的解决数组/列表问题的方法,特别是对于子字符串或子数组问题。这种技巧可以用来解决多种类型的问题,包括最长子串、最小子串、数组和等问题。

滑动窗口的基本思想是维护一个窗口,通常在数组或列表上滑动,用于观察该窗口内的元素。窗口的大小、滑动的方式(左滑、右滑或同时)取决于具体问题。

以下是一个滑动窗口技巧的通用算法框架:

  1. 定义两个指针,一个用于表示窗口的左端,另一个表示窗口的右端。初始化都指向数组的开始位置。

  2. 将右指针向右移动,扩大窗口,直到窗口内的子数组满足问题的条件。

  3. 当窗口满足条件时,尝试将左指针向右移动,缩小窗口,同时保持窗口仍满足条件。

  4. 记录每次更新窗口时的有用信息。例如,如果你在寻找最长子串,那么应记录满足条件的最长长度。

  5. 将步骤2-4作为循环,直到右指针到达数组的末尾。

function slidingWindow(arr, handleWindow) {
    let left = 0;
    let right = 0;

    while (right < arr.length) {
        // 向右扩展窗口
        let window = arr.slice(left, right + 1);

        // 处理当前窗口。这个函数应该根据具体问题来定义。
        // 它需要接受当前窗口作为参数,并返回一个布尔值,表示窗口是否满足条件。
        let windowSatisfiesConditions = handleWindow(window);

        if (windowSatisfiesConditions) {
            // 如果窗口满足条件,记录结果。
            // 在你的特定实现中,这可能是更新最大/最小长度,和,等等。

            // 然后,从左边开始收缩窗口。
            left++;
        } else {
            // 如果窗口不满足条件,向右扩展窗口。
            right++;
        }
    }
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群