算法中的滑动窗口思想及python实现

本文是对 https://www.bilibili.com/video/BV1V44y1s7zJ/ 视频内容的记录，推荐观看原视频加深理解。

滑动窗口问题的特征：

滑动窗口指在数组上通过双指针同向移动而解决的一类问题。两个指针之间的部分可以看做为窗口。
滑动窗口算法一般用来寻找:

满足某一条件的（计算结果、出现次数、同时包含……）
最短的/最长的
子数组/子序列/子串（通常是连续的）

核心思想：

寻找最长窗口使用思路：
初始化：左右双指针（L,R）初始化为 0，R向右逐步移动

循环：在每次移动过程中
如果窗内元素满足条件，R继续向右移动扩大窗口，并更新最优结果；
如果窗内元素不满足条件，则L向右移动缩小窗口。当L,R重合后，R继续右移。

终止：R到达结尾。
寻找最短窗口使用思路：
初始化：左右双指针（L,R）初始化为 0，R向右逐步移动

循环：在每次移动过程中

如果窗内元素满足条件，L向右移动缩小窗口，并更新最优结果。当L,R重合后，R继续右移；
如果窗内元素不满足条件，R向右移动扩大窗口。

终止：R到达结尾。

代码模板：

寻找最长模板：

初始化 left，right，result， best_result

while right < len(arr):
	窗口扩大，加入right对应元素，更新当前result
	while result不满足要求：
		窗口缩小，移除left对应元素，left右移
  
	更新最优结果best_result
	right右移

返回best_result

寻找最短模板：

初始化 left，right，result， best_result

while right < len(arr):
	窗口扩大，加入right对应元素，更新当前result
	while result满足要求：
  	更新最优结果best_result
		窗口缩小，移除left对应元素，left右移
	
	right右移

返回best_result

示例：

最长：https://leetcode.cn/problems/max-consecutive-ones-iii/

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回数组中连续 1 的最大个数。

示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

转换题意：问题可以理解为寻找最多包含k个0的最长子数组
```
class Solution:
  def longestOnes(self, nums: List[int], k: int) -> int:
      left, right= 0, 0
      count= 0  # 当前子序列中0的个数
      max_length = 0

      while right < len(nums):
          if nums[right] == 0:  # 子序列中0的个数增加
              count += 1
          while count > k:  # 当子序列中0的个数大于k时，left右移
              if nums[left] == 0:
                  count -= 1
              left += 1

          max_length = (right - left + 1)  if max_length == 0 else max(max_length, right -left + 1)
          right += 1

      return max_length
```

最短：https://leetcode.cn/problems/minimum-size-subarray-sum/

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
      left, right = 0, 0
      current_sum = 0  # 记录当前子数组的和
      min_length = 0  # 结果
      while right < len(nums):
          current_sum += nums[right]  # right右移，同时计算当前子数组和
          while current_sum >= target:  # 子数组满足条件时
              if right -left + 1 < min_length or min_length == 0:  # 更新结果
                  min_length = right - left + 1
              current_sum -= nums[left]  # left右移并更新当前和
              left += 1
          right += 1
      
      return min_length

固定长度滑动窗口：https://leetcode.cn/problems/sliding-window-maximum/

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]

对于每个窗口中找最大值，如果使用朴素的遍历算法会导致最终算法超时，这里使用大顶堆维护每个窗口中的元素，然后滑动窗口。
```
import heapq

class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      n = len(nums)
      # 注意 Python 默认的优先队列是小根堆，先对nums中的元素取反，然后堆化
      q = [(-nums[i], i) for i in range(k)]
      heapq.heapify(q)

      ans = [-q[0][0]]  # 取对顶元素，取反得到最大值
      for i in range(k, n):  # 滑动窗口，i == right
          heapq.heappush(q, (-nums[i], i))  # right元素加入窗口
          while q[0][1] <= i - k:
              heapq.heappop(q)  # 如果堆顶元素不在窗口中（下标小于等于i-k），将其去除，相当于移动left
          ans.append(-q[0][0])
      
      return ans
```

算法中的滑动窗口思想及python实现

Python相关栏目本月热门文章