滑动窗口(思路 + 模板)
笔者最早接触滑动窗口是滑动窗口协议,滑动窗口协议(Sliding Window Protocol),属于 TCP 协议的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。 发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同,但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。
我们算法中的滑动窗口也是类似,只不过包括的情况更加广泛。实际上上面的滑动窗口在某一个时刻就是固定窗口大小的滑动窗口,随着网络流量等因素改变窗口大小也会随着改变。接下来我们讲下算法中的滑动窗口。

介绍

滑动窗口是一种解决问题的思路和方法,通常用来解决一些连续问题。 比如 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表

常见套路

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”,“连续子数组 xxxx”,就应该可以想到滑动窗口。能不能解决另说,但是这种敏感性还是要有的。
从类型上说主要有:
  • 固定窗口大小
  • 窗口大小不固定,求解最大的满足条件的窗口
  • 窗口大小不固定,求解最小的满足条件的窗口(上面的 209 题就属于这种)
后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的,不一样的仅仅是代码细节。

固定窗口大小

对于固定窗口,我们只需要固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点,并且保证:
  1. 1.
    l 初始化为 0
  2. 2.
    初始化 r,使得 r - l + 1 等于窗口大小
  3. 3.
    同时移动 l 和 r
  4. 4.
    判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足,再判断是否需要更新最优解,如果需要则更新最优解
    • 4.2 如果不满足,则继续。

可变窗口大小

对于可变窗口,我们同样固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点。后面有所不同,我们需要保证:
  1. 1.
    l 和 r 都初始化为 0
  2. 2.
    r 指针移动一步
  3. 3.
    判断窗口内的连续元素是否满足题目限定的条件
    • 3.1 如果满足,再判断是否需要更新最优解,如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 3.1
    • 3.2 如果不满足,则继续。
形象地来看的话,就是 r 指针不停向右移动,l 指针仅仅在窗口满足条件之后才会移动,起到窗口收缩的效果。

模板代码

伪代码

1
初始化慢指针 = 0
2
初始化 ans
3
4
for 快指针 in 可迭代集合
5
更新窗口内信息
6
while 窗口内不符合题意
7
扩展或者收缩窗口
8
慢指针移动
9
更新答案
10
返回 ans
Copied!

代码

以下是 209 题目的代码,使用 Python 编写,大家意会即可。
1
class Solution:
2
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
3
l = total = 0
4
ans = len(nums) + 1
5
for r in range(len(nums)):
6
total += nums[r]
7
while total >= s:
8
ans = min(ans, r - l + 1)
9
total -= nums[l]
10
l += 1
11
return 0 if ans == len(nums) + 1 else ans
Copied!

题目列表(有题解)

以下题目有的信息比较直接,有的题目信息比较隐蔽,需要自己发掘

扩展阅读

最近更新 1yr ago