1.滑动窗口模板回顾
left = 0
right = 0
while right < len(nums):
right_ele = s[right]
# 无脑将right_ele纳入窗口。这表示需要更新当前窗口的各种必要状态
window.add(right_ele)
# 如果在前面增大窗口后，发现可以缩小窗口
if window needs shrink:
while left <= right or any other condition:
left_ele = s[left]
# 无差别自增left
left += 1
# 无脑将left_ele踢出窗口。这表示需要更新当前窗口的各种必要状态（增大窗口时更新了啥现在也得更新啥）
window.remove(left_ele)
# 如果发现窗口缩小后不满足窗口限制条件了，break
if window does not need shrink:
break
# 无差别自增right
right += 1
整个过程可以这样理解
- right指针总是主动探索新世界，对应外层while的最后一句代码 right += 1实现无差别自增right
- 而left总是被动地增长，被right的探索行为牵引着前进
要注意到，right的每一次增长都是自增1；而left每一次增长的幅度不定，由窗口的shrink condition决定。
也就是说，滑动窗口的本质是——
当我们以滑动窗口的方法去遍历一个区间，实际就是用right指针进行遍历，通过right自增1实现遍历区间的每一个元素。只是在遍历的同时，我们又寻找了当前元素对应的left端点。而且，left，right都不走回头路
当遍历完成后，我们就找到了以每个元素为右端点的所有窗口
2.例
2.1 992. K 个不同整数的子数组
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
最直观的做法，遍历A的所有区间（时间复杂度O(n2)），进行set()操作（时间复杂度O(n)），判断集合大小与K的关系，总时间复杂度O(n3)。可以优化，遍历数组A，以当前元素为左边界（或者右边界），找到包含K个整数的区间，然后访问下一元素，时间复杂度O(n^2)
class Solution:
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
l = len(A)
res = 0
for i in range(l):
left, right = i, i
window = set()
while True:
if right >= l:
break
window.add(A[right])
cnt = len(window)
if cnt == K:
res += 1
elif cnt < K:
pass
else:
break
right += 1
return res
提交超时，再继续优化。1.上面的想法有一点像滑动窗口，2.而且这种连续子数组的题目，也适用滑动窗口，3.加上滑动窗口时间复杂度O(n)。种种迹象表明，应该要往滑动窗口去想
基于滑动窗口的思路，我们尝试以right遍历到的元素为区间的右边界，需要确定区间左边界，保证区间[?, right]内仅含有K个整数。显然，？指向的合法位置可能不止一个。这样一来，当right自增时，left反而有可能需要倒退，这样时间复杂度就未必是O(n)了，也脱离了滑动窗口的模板。这时我们转化一下题目，给定数组A，求最多包含K个整数的子字符串个数总数，就可以用滑动窗口了。对于每个right遍历到的数，求其最远的左边界，满足所得区间的不同整数个数不大于K，则当right自增时，新的左边界不可能比上一左边界更左，即left不会走回头路，如下：
# 返回最多包含K个整数的连续子数组个数
def maxSubarraysWithKDistinct(A, K):
l = len(A)
res = 0
# 边界条件
if l == 0:
return res
left, right = 0, 0
window = dict()
while right < l:
ele = A[right]
if ele not in window:
window[ele] = 0
window[ele] += 1
size = len(window)
# 左边界扩张
while size > K:
window[A[left]] -= 1
if window[A[left]] == 0:
window.pop(A[left])
size = len(window)
left += 1
right += 1
res += right - left
return res
有了这个函数，利用
maxSubarraysWithKDistinct(A, K) - maxSubarraysWithKDistinct(A, K-1)
就得到不同整数的个数恰好为 K的所有子数组个数
2.2 424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度
思路：
找到所有这样的窗口，能够在除去其内部数量最多的元素，剩余元素的数量<=k。从中得到最大的窗口即可
套滑动窗口模板，求出以每个字符为右边界时的最大窗口，过程中不断更新窗口最大值
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
num = [0] * 26
n = len(s)
maxn = left = right = 0
res = 0
while right < n:
num[ord(s[right]) - ord("A")] += 1
# 求最多元素的数量
maxn = max(maxn, num[ord(s[right]) - ord("A")])
# 剩余元素与k对比
while right - left + 1 - maxn > k:
num[ord(s[left]) - ord("A")] -= 1
left += 1
right += 1
res = max(res, right-left)
return res
这里有个trick可以继续优化——
因为我们要的是最大的窗口，因此当发现nums[i+1]为右边界时的窗口要比nums[i]为右边界的窗口更小时，我们没有必要将原来大的窗口变小，只需要平移原来的窗口。怎么做到平移呢？很简单，我们知道模板里right是每次自增1，而left则每次自增若干，那么我们发现窗口要shrink时，left也自增1就好了而无需频繁移动。这样left和right同时自增1，实现了窗口平移，这样整个滑动过程中，窗口只会不断变大而不会缩小
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
num = [0] * 26
n = len(s)
maxn = left = right = 0
while right < n:
num[ord(s[right]) - ord("A")] += 1
# 求最多元素的数量
maxn = max(maxn, num[ord(s[right]) - ord("A")])
# 剩余元素与k对比。【while 改 if，使得left只自增1】
if right - left + 1 - maxn > k:
num[ord(s[left]) - ord("A")] -= 1
left += 1
right += 1
return right - left
网友评论