题记
滑动窗口每次做完，过一段时间又忘了，所以还是需要在一起总结一下。
模板
参考资料：https://leetcode-cn.com/problems/longest-substring-with-at-most-two-distinct-characters/solution/hua-dong-chuang-kou-zhen-di-jian-dan-yi-73bii/
上面链接中的内容很多，感觉有点冗余，这里我认为只需要记住写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def problemName(self, s: str) -> int:
# Step 1. 初始化
res = 0
i = 0
window = {}
for j in range(len(s)):
# Step 2: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
x = new_x
if condition:
y = new_y
'''
------------- 下面是两种情况，读者请根据题意二选1 -------------
'''
# Step 3 - 情况1 题目要求滑动框固定
if 窗口长度大于限定值:
# 更新 (部分或所有) 维护变量
# 窗口左指针前移一个单位保证窗口长度固定
# Step 3 - 情况2 维护一个可变长的合法的滑动窗
while 不合法:
window[i] = ... # 更新 (部分或所有) 维护变量
i += 1
return res
|
滑动窗变长
159. 至多包含两个不同字符的最长字串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
i, j = 0, 0
window = {} # 元素和它最后一个的位置
kind = 0
res = 0
for j in range(len(s)):
if s[j] not in window or window[s[j]] == 0:
window[s[j]] = 1
kind += 1
else:
window[s[j]] += 1
while kind >= 3:
window[s[i]] -= 1
if window[s[i]] == 0:
kind -= 1
i += 1
res = max(res, j-i+1)
return res
|
感想
- 这种有元素种类限制的题目，用一个变量
kind存，比用len(window)要好，因为滑动窗口左边弹出元素的临界值是window[x]==0，这个时候还要弹出这个元素，容易出错
- 注意不要忽略条件
window[s[j]] == 0，这种情况虽然元素还在window里，但是相当于没有。
209. 长度最小的子数组（≥target）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
i = 0
res = float('inf')
cur_sum = 0
for j in range(len(nums)):
cur_sum += nums[j]
while cur_sum >= s:
cur_sum -= nums[i]
res = min(res, j-i+1)
i += 1
if res == float('inf'):
return 0
return res
|
感想
和模板不太一样，因为要求的是最短的长度，所以res的更新在while循环中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
zero_count = 0
res = 0
i = 0
for j in range(len(nums)):
if nums[j] == 0:
zero_count += 1
while zero_count == 2:
if nums[i] == 0:
zero_count -= 1
i += 1
res = max(res, j-i+1)
return res
|
这题的变形是1004. 最大连续1的个数 III，基本上一摸一样的写法，就是最多1个0，变成最多k个0.
感想
和159类似，但是这里想到了其他更新i的方法，结果并不对，变长滑动窗口还是要老老实实用while循环一步步更新i的值直到条件满足，这样不容易出错。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
i = 0
res = 0
window = set()
for j in range(len(s)):
while s[j] in window:
window.remove(s[i])
i += 1
window.add(s[j])
res = max(res, j-i+1)
return res
|
感想
这道题在滑动窗口中出现的频率最高，不过代码其实不太套路化，可以看到前面的所有题目，都是对window 操作之后，再做while。代码上这道题是相反的，但是逻辑上，同样也是先把num[j]放进去，但是因为这里用的是set，所以要在后面放入num[j]。
滑动窗固定
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
i = 0
cur_sum = sum(nums[:k])
res = cur_sum
for j in range(k, len(nums)):
cur_sum -= nums[i]
cur_sum += nums[j]
res = max(cur_sum, res)
i += 1
return res / k
|
感想
一道简单题，但是要注意这里滑动窗口一开始就初始化了前k个。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
res = 0
i = 0
cur_sum = 0
for j in range(len(s)):
cur_sum += abs(ord(s[j]) - ord(t[j]))
while cur_sum > maxCost:
cur_sum -= abs(ord(s[i]) - ord(t[i]))
i += 1
res = max(res, j-i+1)
return res
|
感想
看到子字符串，要想到可能可以用到滑动窗。如果不知道能用滑动窗，感觉还是挺难写出来的。
典型的固定长度的滑动窗，并且是出题频率最高的。与其说是滑动窗口，其实是单调队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
i = 0
window = collections.deque()
for j in range(len(nums)):
if window and j - window[0] >= k:
window.popleft()
while window and nums[window[-1]] <= nums[j]:
window.pop()
window.append(j)
if j >= k - 1:
res.append(nums[window[0]])
return res
|
感想
记得构建的是一个左大右小的队列，答案是队列的最大值。