二十、滑动窗口

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

1.滑动窗口算法

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

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

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

• 定义两个指针，一个用于表示窗口的左端，另一个表示窗口的右端。初始化都指向数组的开始位置。
  
• 将右指针向右移动，扩大窗口，直到窗口内的子数组满足问题的条件。
  
• 当窗口满足条件时，尝试将左指针向右移动，缩小窗口，同时保持窗口仍满足条件。
  
• 记录每次更新窗口时的有用信息。例如，如果你在寻找最长子串，那么应记录满足条件的最长长度。
  
• 将步骤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++;
        }
    }
}

2.滑动窗口最大值

给定一个整数数组nums和一个整数k，请找出所有滑动窗口大小为k的子数组中的最大值。

1）题目描述：

给定一个整数数组nums和一个整数k，请你找出所有滑动窗口大小为k的子数组中的最大值。滑动窗口是一个固定大小的窗口，它通过在数组上滑动，每次滑动一个位置，来扫描数组中的元素。你需要返回每个滑动窗口中的最大值。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7]，k = 3 输出：[3,3,5,5,6,7] 解释：滑动窗口的位置从左到右分别为：[1,3,-1]，[3,-1,-3]，[-1,-3,5]，[-3,5,3]，[5,3,6]，[3,6,7]。每个窗口中的最大值分别为3，3，5，5，6，7。

输入：nums = [1], k = 1 输出：[1]

带你读《图解算法小抄》二十、滑动窗口（2）https://developer.aliyun.com/article/1347999?groupCode=tech_library