数据结构与算法——滑动窗口
滑动窗口也是同向双指针,通常的技巧是移动右端点r,维护左端点l,使得窗口内的数据始终满足题目的要求,滑动窗口的题型一般可以分为两大类,定长滑动窗口和不定长滑动窗口,要注意的是:如果数组中有负数,一般是不能进行滑窗的,因为在移动右端点时如果有负数可能导致窗口内的数据不满足单调性。这里为大家提供定长滑动窗口和不定长滑动窗口的两个模版,便于大家解决相关题目。
·
滑动窗口也是同向双指针,通常的技巧是移动右端点r,维护左端点l,使得窗口内的数据始终满足题目的要求,滑动窗口的题型一般可以分为两大类,定长滑动窗口和不定长滑动窗口,要注意的是:如果数组中有负数,一般是不能进行滑窗的,因为在移动右端点时如果有负数可能导致窗口内的数据不满足单调性。
这里为大家提供Python实现的定长滑动窗口和不定长滑动窗口的两个模版,便于大家解决相关题目,首先是定长滑动窗口的模版:
# 定长滑动窗口模版,以力扣643题为例
# 给你一个由 n 个元素组成的整数数组nums和一个整数k,请你找出平均数最大且长度为k的连续子数组,
# 并输出该最大平均数。
# 初始化答案ans,左端点l以及当前滑动窗口内的数字之和total
ans = -inf
total = l = 0
# 枚举右端点和对应值
for r, n in enumerate(nums):
# 将元素加入滑动窗口,并将其元素值加入total
total += n
# 如果当前子数组长度大于k,则不满足题目的长度要求,移动左端点l,并维护total值
if r - l + 1 > k:
total -= nums[l]
l += 1
# 如果子数组长度等于k,满足长度要求,计算当前平均数并更新答案
if r - l + 1 == k:
ans = max(ans, total / k)
return ans
学习完本模版后,大家可以用它去秒杀力扣1343、2090、2379等题目,只需要改变ans的结构、滑动窗口内维护的数据以及满足题目的判定条件即可。
不定长滑动窗口模版如下:
# 不定长滑动窗口模版,以力扣3090题为例
# 给你一个字符串s ,请找出满足每个字符最多出现两次的最长子字符串,并返回该子字符串的最大长度。
# 使用一个默认字典hm存储滑动窗口内各个字符的数量
hm = defaultdict(int)
# 初始化左端点l和答案ans
l = ans = 0
# 枚举右端点和对应字符
for r, c in enumerate(s):
# 将当前元素加入滑动窗口,并在hm中加入该元素
hm[c] += 1
# 维护左端点,直到窗口内的元素数量满足题目要求
while hm[c] > 2:
hm[s[l]] -= 1
l += 1
# while循环结束后,更新答案ans
ans = max(ans, r - l + 1)
return ans
学习完本模版后,大家可以用它去秒杀力扣3、1208、1493等题目,同样只需要改变ans的结构、滑动窗口内维护的数据以及满足题目的判定条件即可。
更多推荐
所有评论(0)