calendar_month  schedule  edit_square266 字 
🤖 AI文章摘要 gemini-2.0-flash-lite

这篇文章介绍了滑动窗口的概念及其在解决问题中的应用。滑动窗口是一种用于处理数组或字符串等数据结构的技术，通过维护一个窗口来遍历数据，从而优化计算效率。文章首先解释了滑动窗口适用的两种情况：需要重复计算重叠区间数据的数据状态，以及重复区间数据具备数据相关性。

文章接着介绍了两种类型的滑动窗口：

  1. 定长滑动窗口：适用于重叠数据区间长度一致的情况。通过确定窗口大小，计算第一个窗口的结果，然后通过循环移动窗口并利用上个窗口的计算结果计算当前窗口的结果。
  2. 可变滑动窗口：适用于重叠数据区间长度不一致的情况。使用双指针来操作窗口的大小以及移动窗口，通过移动右指针扩展窗口，移动左指针缩小窗口，直至窗口计算结果符合条件。

文章还提供了两个使用示例，分别展示了定长滑动窗口和可变滑动窗口的应用：

  • 示例1：非负数组arr长度为k的子组数中，求和的最大值。通过定长滑动窗口优化，将时间复杂度从O(k*n)降低到O(n)。
  • 示例2：非负数组arr求和大于k的子数组中，长度的最小值。通过可变滑动窗口优化，将时间复杂度从O(n^2)降低到O(n)。
此内容根据文章生成，并经过人工审核，仅用于文章内容的解释与总结 投诉
deeb1225cd5586be2f2fca10f93c60d4

滑动窗口

窗口的作用在于标记区间的元素并存储窗口当前的数据状态，窗口滑动时利用相邻窗口的相关性计算下一个窗口的数据状态来提高计算效率。

滑动窗口适用于以下问题情形：

  • 需要重复计算重叠区间数据的数据状态。
  • 重复区间数据具备数据相关性。

定长滑动窗口

定长滑动窗口适用于重叠数据区间长度一致的情况。

  • 确定窗口大小，假设为$w$。
  • 计算第一个窗口的结果并进行存储。
  • 通过循环逐步移动窗口并通过上个窗口的计算结果计算出当前窗口的结果。

可变滑动窗口

可变滑动窗口适用于重叠数据区间长度不一致的情况，可变滑动窗口使用了双指针来操作窗口的大小以及移动窗口。

  • 通过移动窗口右指针扩展窗口，通过移动左指针缩小窗口，直至窗口计算结果符合条件。
  • 如果计算结果符合条件，进行相应的处理后，移动左指针重复步骤1。
  • 重复步骤1和步骤2，直到所有数据被处理。(结束条件根据问题需求而定)

使用示例

滑动窗口示例1

非负数组arr长度为k的子组数中，求和的最大值 传统的思路是循环所有子数组起始位置时内嵌循环进行子数组的求和叠加并进行最大值比较，假设子数组长度为$k$,这个方法的时间复杂度为$O(k*n)$。可以发现子数组间存在数据重叠求和进行了很多重复的加法计算，优化的思路是使用定长滑动窗口的思想缓存和复用累加结果，优化后的时间复杂度为$O(n)$。


def subarr_max_sum(arr, k):
  n = len(arr)
  if n <= k:
    return -1
  window_sum = 0
  max_sum = window_sum
  # cache current window result
  window_sum = sum(arr[0:k])
  for i in range(n-k):
    window_sum = window_sum - arr[i] + arr[i+k]
    max_sum = max(window_sum, max_sum)
  return max_sum
# Driver code
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
print(subarr_max_sum(arr, k))

滑动窗口示例2

非负数组arr求和大于k的子数组中，长度的最小值
传统的思路是循环所有子数组起始位置时循环累加起始位置后面的元素至求和刚大于k时，比较并记录当前长度，这个方法的时间复杂度为$O(n^2)$。可以发现子数组累加时进行了很多重复的加法计算，优化的思路是使用可变滑动窗口的思想缓存和复用累加结果，但这里使用的是可变滑动窗口求解，优化后的时间复杂度为$O(n)$。


def subarr_min_len(arr, x):
  n = len(arr)
  i, j = 0, 0
  sum = 0
  min_len = float('inf')
  while j < n:
    # move right pointer to increase the sum, 
    # when the sum is greater than x, the elements
    # after current j are ignored. 
    while j < n and sum <= x:
      sum += arr[j]
      j = j + 1

    # when we reach the end of the array,
    # and the sum is smaller than x,
    # the rest of cases are ignored.
    if j == n and sum  <= x:
      break

    # move left pointer to decrease the sum, 
    # when the sum is smaller than x, the element 
    # before current i are ignored. 
    while i < j and sum - arr[i] > x:
      sum -= arr[i]
      i = i + 1
    
    min_len = min(min_len, j - i)

    # move left pointer
    sum -= arr[i]
    i += 1
  if  min_len == float('inf'):
    return 0
  return min_len
# Driver code
arr = [1, 4, 45, 6, 10, 19]
x = 51
print(subarr_min_len(arr, x))