3. Longest Substring Without Repeating Characters

以右指针为基准遍历扩大窗口，每次加入字符后判断是否出现重复，若是则不断移动左指针缩小窗口。

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         res = 0
  4.         dic = set()
  6.         l = 0
  7.         for r, c in enumerate(s):
  8.             while c in dic:
  9.                 dic.remove(s[l])
  10.                 l += 1
  11.             dic.add(c)
  12.             res = max(res, r - l + 1)
  14.         return res
  • 时间复杂度：滑动窗口 - 图1
  • 空间复杂度：滑动窗口 - 图2

76. Minimum Window Substring

使用freq记录每个字符对应的还需要填充频数，cnt记录子串t中字符还需要填充的总频数。
需要注意在扩大和缩小窗口时，不要忘记改变cnt的判断。
特殊用例：
s == "a" t == "a"
故不可将min_len设置为len(s)

  1. from math import inf
  2. from collections import Counter
  4. class Solution:
  5.     def minWindow(self, s: str, t: str) -> str:
  6.         freq = Counter(t)                        # window中还需要的char数量
  7.         cnt = len(t)                             # window中还需要的char数量总和
  8.         res, min_len = '', inf
  9.         l = 0
  11.         for r, c in enumerate(s):                # 扩大窗口，尝试覆盖t
  12.             if freq[c] > 0:                      # 判断是否是t中字符
  13.                 cnt -= 1
  14.             freq[c] -= 1
  16.             while cnt == 0:                      # 已完全覆盖子串，开始缩小窗口
  17.                 if (cur_len := r-l+1) < min_len:
  18.                     min_len = cur_len
  19.                     res = s[l:r+1]
  20.                 if freq[s[l]] == 0:              # 判断是否是t中字符
  21.                     cnt += 1
  22.                 freq[s[l]] += 1
  23.                 l += 1
  25.         return res
  • 时间复杂度：滑动窗口 - 图3
  • 空间复杂度：滑动窗口 - 图4

643. Maximum Average Subarray I

  • 滑动窗口裸题
    • 初始化将滑动窗口压满，取得第一个滑动窗口的目标值
    • 继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素

  • 前缀和（次优解）

    • substring子串，subarray子数组: 连续

    • subsequence子序列: 不一定连续

      1. class Solution:
      2. def findMaxAverage(self, nums: List[int], k: int) -> float:
      3.    res = window = sum(nums[:k])
      5.    for i in range(k, len(nums)):
      6.        window += nums[i] - nums[i-k]
      7.        res = max(res, window)
      9.    return res / k

  • 时间复杂度：滑动窗口 - 图5

  • 空间复杂度：滑动窗口 - 图6

567. Permutation in String

限定了字符串只包含小写字母，故使用两个长度为26的频数数组来记录。

  1. class Solution:
  2.     def checkInclusion(self, s1: str, s2: str) -> bool:
  3.         m, n = len(s1), len(s2)
  4.         if m > n:
  5.             return False
  6.         cnt_1 = [0] * 26
  7.         cnt_2 = [0] * 26
  9.         for i in range(m):                         # 压满窗口（以s1为基准）
  10.             cnt_1[ord(s1[i]) - ord('a')] += 1
  11.             cnt_2[ord(s2[i]) - ord('a')] += 1
  12.         if cnt_1 == cnt_2:
  13.             return True
  15.         for i in range(m, n):                      # 向右移动窗口
  16.             cnt_2[ord(s2[i]) - ord('a')] += 1
  17.             cnt_2[ord(s2[i-m]) - ord('a')] -= 1
  18.             if cnt_1 == cnt_2:
  19.                 return True
  21.         return False
  • 时间复杂度：滑动窗口 - 图7
  • 空间复杂度：滑动窗口 - 图8

239. Sliding Window Maximum

Approach I** 优先队列（堆）
使用一个大顶堆记录窗口中的最大值：每次首先加入元素（取反是因为Python的默认heapq实现是小顶堆）与索引，然后循环**判断堆顶元素是否在窗口内（只能删除堆顶元素来保证堆性质，循环删除是因为某个较大元素而导致累积了较多的元素在窗口内）。

  1. import heapq
  3. class Solution:
  4.     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
  5.         max_heap = [(-nums[i], i) for i in range(k)] # 记录index:
  6.         heapq.heapify(max_heap)                      # 为了判断堆顶元素是否在窗口中
  7.         res = [-max_heap[0][0]]
  9.         for i in range(k, len(nums)):
  10.             heapq.heappush(max_heap, (-nums[i], i))
  11.             while max_heap[0][1] <= i-k:             # 循环：堆顶元素不在窗口，可永久删除
  12.                 heapq.heappop(max_heap)              # 使用while而非if
  13.             res.append(-max_heap[0][0])
  15.         return res
  • 时间复杂度：滑动窗口 - 图9，每次调整堆滑动窗口 - 图10
  • 空间复杂度：滑动窗口 - 图11，注意到可能会有冗余元素（不在窗口中）存在堆中，故空间复杂度不是滑动窗口 - 图12

Approach II** 单调队列（双端队列deque实现）
考虑滑动窗口内的两个下标滑动窗口 - 图13和滑动窗口 - 图14，如果滑动窗口 - 图15并且滑动窗口 - 图16，那么在窗口右移的过程中，只要滑动窗口 - 图17还在窗口中，滑动窗口 - 图18就必定在窗口中，那么滑动窗口 - 图19的存在就无关紧要了，故可以删去。
考虑使用一个严格单调递减的双端队列，保存数组的索引。在保证队列的最大长度为滑动窗口 - 图20的情况下，队首元素便是窗口内最大值的索引。
滑动窗口 - 图21为什么不用单调栈，而是使用单调队列？
滑动窗口 - 图22本题中有两种弹出数据结构内元素的策略：其一，从右侧弹出，为了保证单调性；其二，从左侧弹出，为了保证窗口大小。故只有双端队列这种数据结构能够满足题设需求。
滑动窗口 - 图23为何队列中保存索引，而不是数值？
滑动窗口 - 图24这是为了存储更多信息**（类似的，单调栈问题也有相同的操作）。有了索引便可以求得对应下标的数值，可以同时完成上一个问题中两个弹出元素的判断过程。

  1. from collections import deque
  3. class Solution:
  4.     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
  5.         queue = deque()                # 严格单调递减 双端队列：保存index
  7.         for i in range(k):             # 初始化：压满滑动窗口
  8.             while queue and nums[queue[-1]] <= nums[i]:
  9.                 queue.pop()
  10.             queue.append(i)
  12.         res = [nums[queue[0]]]
  14.         for i in range(k, len(nums)):  # 滑动，扩大窗口
  15.             while queue and nums[queue[-1]] <= nums[i]: # 维持单调性
  16.                 queue.pop()
  17.             queue.append(i)
  19.             if queue[0] <= i-k:        # 保存index的原因：判断队首元素是否不在窗口中
  20.                 queue.popleft()        # 缩小窗口
  21.             res.append(nums[queue[0]])
  23.         return res
  • 时间复杂度：滑动窗口 - 图25
  • 空间复杂度：滑动窗口 - 图26，极限情况队列保存滑动窗口 - 图27个元素

2024. Maximize the Confusion of an Exam

题目求修改次数不超过k时，连续子串T或者F的最大长度；
等价于求包含T或F个数不超过k时的连续子串最大长度，使用滑动窗口。

  1. class Solution:
  2.     def maxConsecutiveAnswers(self, answer: str, k: int) -> int:
  4.         def max_consecutive_window(ch):
  5.             res = 0
  6.             cnt = 0    # window中包含ch的数量
  7.             l = 0
  8.             for r in range(len(answer)):
  9.                 cnt += answer[r] == ch
  10.                 while cnt > k:
  11.                     cnt -= answer[l] == ch
  12.                     l += 1
  13.                 res = max(res, r-l+1)
  14.             return res
  16.         return max(max_consecutive_window('T'), max_consecutive_window('F'))
  • 时间复杂度：滑动窗口 - 图28
  • 空间复杂度：滑动窗口 - 图29

1004. Max Consecutive Ones III

Approach I** 动态规划（超时） =>
滑动窗口 - 图30：考虑前滑动窗口 - 图31个num（并以滑动窗口 - 图32结尾），最大翻转次数为滑动窗口 - 图33，连续滑动窗口 - 图34的最大长度。

  • 滑动窗口 - 图35，无需消耗反转次数，滑动窗口 - 图36
  • 滑动窗口 - 图37，由于计算连续滑动窗口 - 图38的最大长度必须以滑动窗口 - 图39结尾，故消耗一次翻转次数，滑动窗口 - 图40

    滑动窗口 - 图41的数量级不超过滑动窗口 - 图42的话，动态规划是可行的。

  1. class Solution:
  2.     def longestOnes(self, nums: List[int], k: int) -> int:
  3.         n = len(nums)
  4.         res = 0
  5.         dp = [[0] * (k+1) for _ in range(2)]
  7.         for i in range(1, n+1):
  8.             for j in range(k+1):
  9.                 if nums[i-1] == 1:
  10.                     dp[i&1][j] = dp[(i-1)&1][j] + 1
  11.                 else:
  12.                     dp[i&1][j] = 0 if j == 0 else dp[(i-1)&1][j-1] + 1
  13.             res = max(res, dp[i&1][j])
  15.         return res
  • 时间复杂度：滑动窗口 - 图43
  • 空间复杂度：滑动窗口 - 图44

Approach II** 前缀和+双指针 => 对数**

Approach III** 滑动窗口 => 常数**

  1. class Solution:
  2.     def longestOnes(self, nums: List[int], k: int) -> int:
  3.         res = 0
  4.         cnt = 0    # 窗口中0的数量
  5.         l = 0
  7.         for r, num in enumerate(nums):
  8.             cnt += num == 0
  9.             while cnt > k:
  10.                 cnt -= nums[l] == 0
  11.                 l += 1
  12.             res = max(res, r-l+1)
  14.         return res
  • 时间复杂度：滑动窗口 - 图45
  • 空间复杂度：滑动窗口 - 图46

713. Subarray Product Less Than K

  1. class Solution:
  2.     def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
  3.         if k <= 1:
  4.             return 0
  6.         res = 0   # 记录乘积<k且以右指针j结尾的子数组
  7.         prod = 1
  9.         i = 0
  10.         for j in range(len(nums)):
  11.             prod *= nums[j]
  12.             while prod >= k:
  13.                 prod //= nums[i]
  14.                 i += 1
  15.             res += j - i + 1
  17.         return res
  • 时间复杂度：滑动窗口 - 图47
  • 空间复杂度：滑动窗口 - 图48