系列链接
1.滑动窗口问题（统计型约束的连续子串问题）2020-05-27
2.滑动窗口之再体会-以右为主，都不回头 2021-02-09
在滑动窗口之再体会中，从滑动窗口的【行为角度】对滑动窗口进行了理解——
即，滑动窗口本质上是对一个序列的遍历，遍历了以序列的各个元素为右端点的所有valid situation
本文将从另一角度——数据结构角度，对滑动窗口进行理解
1.滑动窗口的队列本质
滑动窗口，一般的行为都是右边界扩张完成纳入新元素，左边界收缩完成吐出窗内元素。从数据结构的角度看，滑动窗口其实就是一个队列，右边界扩张对应新元素入队，左边界收缩对应元素出队。
滑动窗口多被冠以算法，而从数据结构上认清滑动窗口实为队列，有助于让我们理解算法与数据结构两者密不可分、相辅相成的关系，从而从更深的层次理解问题，拓宽解决问题的思路
2.例
leetcode 995. K 连续位的最小翻转次数
在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
思路：
首先，对于一个长度为l的数组A，一共有 l-K+1 个长度为K的连续子数组。为了保证翻转次数最少，每个这样的子数组至多翻转一次。容易想到，假设整个数组可以翻转为全1，那必然不会只有一种翻转顺序能够实现，因此可以推出先翻谁后翻谁的顺序并不重要。对于若干个K位数组的翻转操作，先后顺序其实并不影响最终翻转的结果。因此，选择从左向右扫描，总之保证i左侧已经翻转好，问题不断坍塌为翻转从i开始的右侧子数组
那么，朴素的解法很容易写出来，从左到右模拟整个翻转过程即可
class Solution:
def minKBitFlips(self, A: List[int], K: int) -> int:
# 0要被翻转奇数次，1要被翻转偶数次
# 从左向右扫描，当前位置i为1则continue，当前位置i为0则将[i, i+k)翻转一次，继续向后。总之保证左侧已经翻转好，问题不断坍塌为翻转从i开始的右侧子数组
l = len(A)
k = K
cnt = 0
for i in range(l):
if A[i] == 1:
continue
else:
# 最后一个可以翻转的子数组以l-k为左端点。如果在l-k后的元素还需要翻转，返回-1
if i > l - k:
return -1
cnt += 1
# 模拟翻转 0->1, 1->0
for j in range(i, i+k):
if A[j] == 0:
A[j] = 1
else:
A[j] = 0
return cnt
但是，提交超时。这是因为整个过程我们进行了大量的翻转，时间复杂度O(N) * O(K)。如果K很大，耗时就上去了。实际上，我们不需要每一次都翻转K位。
我们知道，其实对于元素A[i]，它是否需要翻转取决于2点：
- 1.它本身是0还是1
- 2.它被前面的K-1个数组翻转了几次
第1点我们好解决，直接访问数组A就可以拿到；关键是第二点怎么办？我们先直观地感受一下，整个翻转的过程长什么样，是不是就像一个定长为K的窗口沿着数组A向右滑动，被窗口圈中的部分判断是否需要翻转。现在我们不模拟整个翻转过程了，对于我每个A[i]，只需要知道我被前面的K-1个元素翻转了多少次，而这前K-1个连续元素，也是随着i的右移而整体右移的，是不是像滑动窗口一样？或者说，它就是滑动窗口
好，现在我们维护一个队列作为if_reverse_window，长度为K-1。遍历至A[i]时，对window求和，得到它被前面的K-1个数组翻转了几次；再结合A[i]的值，判断以A[i]为起点的连续K位子数组是否需要翻转。如翻转，1入队window，res ++ ；不翻转，0入队window。注意维护window的大小，当window长度大于K-1时，出队最左侧元素。
维护一个翻转次数窗口，用入队、出队这样的O(1)操作替代O(K)的模拟翻转，滑动窗口的队列本质，体会到了吗？
class Solution:
def minKBitFlips(self, A: List[int], K: int) -> int:
# 0要被翻转奇数次，1要被翻转偶数次
# 总则：从左向右扫描，总之保证左侧已经翻转好，问题不断坍塌为翻转从i开始的右侧子数组
l = len(A)
from collections import deque
# 因为当前元素是否需要翻转受到前K-1个元素影响，所以reverse_window记录前K-1个元素的翻转次数，即reverse_window最大长度为K-1
if_reverse_window = deque([])
pre_reverse_cnt = 0
res = 0
for i in range(l):
## 1.判断当前元素是否需要翻转
# 当前元素为0且已经被翻转偶数次，或者当前元素为1且已经被翻转奇数次，则需要再次翻转
if (pre_reverse_cnt + A[i]) % 2 == 0:
if i > l - K:
return -1
res += 1
if_reverse_window.append(1)
pre_reverse_cnt = pre_reverse_cnt + 1
# 当前元素不需翻转
else:
if_reverse_window.append(0)
# 2.更新window后，需要维护window的大小不超过K
if len(if_reverse_window) > K-1:
ele2pop = if_reverse_window.popleft()
pre_reverse_cnt = pre_reverse_cnt - ele2pop
return res
网友评论