滑动窗口算法思想
source link: https://coolcao.com/2020/04/30/SlidingWindowAlgorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
滑动窗口算法思想
滑动窗口算法思想是非常重要的一种思想，可以用来解决数组，字符串的子元素问题。它可以将嵌套循环的问题，转换为单层循环问题，降低时间复杂度，提高效率。
滑动窗口的思想非常简单，它将子数组（子字符串）理解成一个滑动的窗口，然后将这个窗口在数组上滑动，在窗口滑动的过程中，左边会出一个元素，右边会进一个元素，然后只需要计算当前窗口内的元素值即可。
可用滑动窗口思想解决的问题，一般有如下特点：
- 窗口内元素是连续的。就是说，抽象出来的这个可滑动的窗口，在原数组或字符串上是连续的。
- 窗口只能由左向右滑动，不能逆过来滑动。就是说，窗口的左右边界，只能从左到右增加，不能减少，即使局部也不可以。
- 使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
- 先不断地增加 right 指针扩大窗口 [left, right]，直到窗口符合要求
- 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，我们都要更新一轮结果。
- 重复第 2 和第 3 步，直到 right 到达尽头。
第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。 左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
left,right := 0,0 // 左右指针
// 窗口右边界滑动
for right < length {
window.add(s[right]) // 右元素进窗
right++ // 右指针增加
// 窗口满足条件
for valid(window) && left<right {
... // 满足条件后的操作
window.remove(arr[left]) // 左元素出窗
left++ // 左指针移动，直到窗口不满足条件
}
}
- 滑动窗口适用的题目一般具有单调性
- 滑动窗口、双指针、单调队列和单调栈经常配合使用
滑动窗口的思路很简单，但在leetcode上关于滑动窗口的题目一般都是mid甚至hard的题目。其难点在于，如何抽象窗口内元素的操作，验证窗口是否符合要求的过程。
即上面步骤2，步骤3的两个过程。
说的有点生涩。来两个例子说明一下。
连续子数组的最大和
给定一个整数数组，计算长度为n的连续子数组的最大和。
比如，给定arr=[1,2,3,4]，n=2，则其连续子数组的最大和为7。其长度为2的连续子数组为[1,2],[2,3],[3,4]，和最大就是3+4=7。
所有问题都可以用穷举法解决，比如这个。我们可以穷举出所有长度为n的子数组，然后计算每个子数组的和，再求最大值。穷举法能实现，但是效率非常低。因为在穷举的过程中会嵌套循环。
滑动窗口的思想就是，把这个要求和的子数组当成一个窗口，然后在数组上滑动。如下图所示：
我们维护一个长度为2的窗口，然后依次滑动这个窗口直至结束。在滑动时，出一个左边元素，进一个右边元素，计算这个窗口内的元素和，然后和最大和比较。滑动结束，也就求出了最大和是多少。
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
27
func maxSubSum(nums []int, n int) int {
if n <= 0 {
return 0
}
if n >= len(nums) {
n = len(nums)
}
// sum 标记窗口内元素和
// maxSum标记sum的最大值
sum, maxSum := 0, 0
// 初始化窗口
for i := 0; i < n; i++ {
sum += nums[i]
}
maxSum = sum
// 滑动窗口
for i := n; i < len(nums); i++ {
// 左出右进
sum = sum - nums[i-n] + nums[i]
if sum > maxSum {
maxSum = sum
}
}
return maxSum
}
和为target的连续正整数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]限制：
1 <= target <= 10^5
这个题目和上面这个就不大一样了。上面这个窗口的长度是固定的n，而这个，不是固定的。
对于滑动窗口思想，有一点需要记住：窗口只能从左到右，沿一个方向滑动。
由于窗口长度不定，所以，这里分三种情况：
- 窗口内元素和小于target，需要扩大窗口。窗口右边界移动。
- 窗口内元素和大于target，需要缩小窗口。窗口左边界移动。
- 窗口内元素和等于target，记录结果。窗口向右滑动。
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
27
28
29
30
31
32
33
34
35
36
37
38
func findContinuousSequence(target int) [][]int {
// 记录窗口内元素和
sum := 0
left, right := 1, 3
for i := 1; i < right; i++ {
sum += i
}
result := [][]int{}
for left <= target-1 {
if sum == target {
tmp := make([]int, right-left)
for i := left; i < right; i++ {
tmp[i-left] = i
}
result = append(result, tmp)
// 窗口向右滑动
left, right = left+1, left+3
sum = (left + left + 1)
} else if sum < target {
// 和小于target，窗口右侧向右移动
sum += right
right++
} else if sum > target {
// 和大于target，窗口左侧向右移动
sum -= left
left++
}
// 如果窗口长度为2，且窗口内元素已经大于target，则可以终止滑动了
if right-left == 2 && sum > target {
break
}
}
return result
}
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
这个问题可以说是上面一个题目的变形，上面一个是和正好等于target，而这个是求和大于等于target的最小子序列长度。
上面这个题目窗口长度是固定的，这个是变长的。但其实利用滑动窗口的思想，难度也算简单。
和上面一个题目一样，我们只需要一个sum变量来存储窗口内元素的和即可。
当sum=s时，此时说明这个窗口是满足条件的，我们要判断此时窗口的长度是否是最小。另外，窗口左边界增加，缩小窗口。
不断重复增大，缩小窗口的操作，直至窗口到数组末尾。时，我们要增大窗口。此时，窗口右边界增加。>
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
27
28
29
30
31
32
33
34
35
func minSubArrayLen(s int, nums []int) int {
length := len(nums)
min := length + 1
// 滑动窗口的左右指针
left, right := 0, 0
// 窗口内元素的和
sum := 0
// 当和小于s时，增大窗口
for sum < s && right < length {
// 如果最小窗口长度已经是1，那么窗口可终止滑动
if min == 1 {
break
}
sum += nums[right]
right++
// 当和大于等于s时，缩小窗口
for sum >= s {
// 比较此时窗口长度与记录的最小长度
if min > right-left {
min = right - left
}
sum -= nums[left]
left++
}
}
if min == length+1 {
return 0
}
return min
}
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
- 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
- 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。1 <= tree.length <= 40000
0 <= tree[i] < tree.length
这个题目，看完描述，都看不明白说的个啥。
其实这个题目很简单，就是说，给定的一个数组，表示果树上结的水果。数组中的每一个不同的值表示一种不同类型的水果。
现在你有两个篮子，需要从前往后收集水果。每个篮子只能装一种水果。收集的时候，需要注意，一个篮子只能装一种水果，且不能丢失重新装。
问最后你能最多装多少个水果。
再说直白点，这个题就是要你从一个整数数组中，找到其只包含两个元素的最长子数组。
理解了题意，这个题就很简单了。
我们定义一个滑动的窗口，表示收集水果的篮子。
如果窗口内收集的水果小于等于两种，那么我们增大窗口。
如果窗口内收集的水果多于两种，那么我们减小窗口。
然后在滑动的过程中，取到窗口的最大长度即可。
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
27
28
29
30
31
32
33
func totalFruit(tree []int) int {
length := len(tree)
max := 0
// basketMap存储窗口内已收集的水果数量
basketMap := map[int]int{}
left, right := 0, 0
// 当窗口内元素个数小于等于2，增大窗口
for right < length && len(basketMap) <= 2 {
rightItem := tree[right]
// 增大窗口，右边元素入窗
basketMap[rightItem]++
right++
// 如果窗口内元素已大于2个，减小窗口
for len(basketMap) > 2 {
leftItem := tree[left]
basketMap[leftItem]--
// 如果左边元素出窗后，该类水果数量已为0，则delete该key
if basketMap[leftItem] == 0 {
delete(basketMap, leftItem)
}
left++
}
current := right - left
if max < current {
// fmt.Printf("left: %d,right: %d\n", left, right)
max = current
}
}
return max
}
最长不重复子串的长度
给定一个字符串str，找出其中不含有重复字符的最长子串的长度。
例如，str=”abcabcdd”，最长不重复子串”abcd”的长度为4。
这个问题和上面一个一样，也是窗口长度不定，需要变长移动窗口。
不断增加窗口长度，如果在增加的过程中，遇到窗口中已经存在的字符，那么，将窗口左侧边界移动到当前已存在新入窗字符的位置。
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
27
28
29
30
31
32
33
34
35
36
37
func lengthOfLongestSubstring(str string) int {
length := len(str)
if length == 0 || length == 1 {
return length
}
left, right := 0, 0
max := right - left
// 窗口，使用map保存在窗口中的子串
windowMap := map[byte]bool{}
for right < length {
// 窗口右侧边界是否在窗口内
if !windowMap[str[right]] {
// 不在窗口内，右侧边界向右移动一格
windowMap[str[right]] = true
right++
// 判断当前窗口长度是否最大
if right-left > max {
max = right - left
}
} else {
// 如果在窗口内，遇到重复的，窗口左侧边界移动到重复字符位置
for left < right {
// 将左侧边界到重复位置的子串移出窗口
windowMap[str[left]] = false
if windowMap[str[left]] == windowMap[str[right]] {
left++
break
}
left++
}
}
}
return max
}
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
这个问题也可以用滑动窗口的思想来解决。因为我们在s2中判断子串是否是s1的排列时，这个子串在s2中一定是连续的。
我们抽象一个窗口，用于记录s1中每个字符应该出现的次数，然后把这个窗口放到s2上滑动判断。
当入窗时，次数减少。因为入窗相当于已经出现。
当出窗时，次数增加。出窗相当于入窗的逆操作。
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
27
28
29
30
31
32
func checkInclusion(s1 string, s2 string) bool {
l1, l2 := len(s1), len(s2)
if l1 > l2 {
return false
}
windowMap := map[byte]int{}
for i := 0; i < l1; i++ {
windowMap[s1[i]]++
}
left, right := 0, 0
for right < l2 {
c := s2[right]
// 入窗操作
windowMap[c]--
right++
// 如果出现次数差值为负数，说明字符出现次数过多。即s2中的这个字符其实在s1中并不存在（或存在，但比s1中个数多）
for left < right && windowMap[c] < 0 {
// 出窗操作
windowMap[s2[left]]++
left++
}
// 如果窗口长度等于s1长度，说明窗口内的这些字符，在s1中都存在，即窗口内字符是s1的一个组合。
if right-left == l1 {
return true
}
}
return false
}
最小覆盖子串
给定一个字符串S，一个字符串T，请在S中找出：包含T所有字母的最小子串。
示例：
输入：S=”ADOBECODEBANC”,T=”ABC”
输出：”BANC”
说明：
如果S中不存在这样的子串，返回空字符串””
如果S中存在这样的子串，我们保证它是唯一的答案。
定义两个变量left,right，区间[left,right]表示窗口。
滑动窗口的right边界，直到窗口内已包含T中所有字符，此时停止right的滑动。
滑动窗口的left边界，直到窗口内不包含T中所有的字符，此时停止left的滑动。
继续上面两个步骤，直接窗口滑动到S的末尾。
滑动left，right边界简单。怎么判断窗口内是否包含T中所有字符呢？
我们可以使用和上面一样的方法。记录字符应该出现的次数。当T的所有字符，在窗口内的次数都大于1时，则说明窗口内已包含T的所有字符。
那么，怎么判断窗口内是否包含T中所有的字符呢？
我们可以使用出现次数来判断，如同上一个题一样。先将T中所有字符出现次数放入哈希表，表示窗口中各个字符应该出现的次数。
当窗口在滑动过程中，遇到T中的字符，那么说明这个字符已经出现，次数减一。当T中所有字符出现次数为0时，说明窗口内已经包含了T中所有的字符。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func minWindow(s string, t string) string {
ls, lt := len(s), len(t)
if ls < lt {
return ""
}
// 窗口里存的是t中字符应该出现的次数
// 正数表示该字符还缺的出现次数，0表示刚好出现，负数表示s中字符出现的次数多于t中字符出现次数
windowMap := map[byte]int{}
// 初始化窗口
for i := 0; i < lt; i++ {
windowMap[t[i]]++
}
windowSize := len(windowMap)
// 其实在go语言里map有零值的概念，这块代码可以不要
// 在其他语言，比如Java的HashMap没有零值概念，需要先初始化一下所有s中的字符出现次数
// for i := 0; i < ls; i++ {
// if _, ok := windowMap[s[i]]; !ok {
// windowMap[s[i]] = 0
// }
// }
left, right := 0, 0
// 窗口中已经包含T的不同字符的种类
c := 0
ans := ""
for right < ls {
// 窗口右边界移动，扩大窗口
windowMap[s[right]]--
// 统计窗口中已经包含的T中的不同字符的种类
if windowMap[s[right]] == 0 {
c++
}
// c==windowSize说明窗口已经包含所有T中的字符
for c == windowSize && windowMap[s[left]] < 0 {
windowMap[s[left]]++
left++
}
if c == windowSize {
if len(ans) == 0 || right-left+1 < len(ans) {
ans = s[left : right+1]
}
}
right++
}
return ans
}
滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:1
2
3
4
5
6
7
8
9> 滑动窗口的位置 最大值
> --------------- -----
> [1 3 -1] -3 5 3 6 7 3
> 1 [3 -1 -3] 5 3 6 7 3
> 1 3 [-1 -3 5] 3 6 7 5
> 1 3 -1 [-3 5 3] 6 7 5
> 1 3 -1 -3 [5 3 6] 7 6
> 1 3 -1 -3 5 [3 6 7] 7
>提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
这个从题目上就说的很直白，滑动窗口的最大值。输入一个数组和一个窗口的长度，然后输出这个窗口依次从左滑动到右时，窗口内的最大值。
这个题目从理解上，比上面这些题目要简单（除了第一个）。因为窗口的长度是固定的，我们在移动时同步移动左右指针即可。唯一的难点在于，怎么选择窗口内的最大值。
循环窗口内所有元素，选择最大值么？当然不是，如果是循环选择最大值的话，那复杂度不就是O(n*k)了么。
除了同步滑动窗口的左右边界，剩下的就是如何在常数时间内获得窗口内的最大值，这个有点像leetcode 155最小栈那个类似，那个是实现一个最小栈，即支持栈的操作，然后可以在常数时间内获取栈内的最小值。这个的话，应该是实现一个最大队列，即支持队列的入队出队，然后在常数时间内获得队列里的最大值。因为这个窗口的滑动本身就是一个队列的操作，滑动一次，就是一个入队出队操作。
这里我们使用双端队列来实现。由于golang中没有原生实现双端队列这个结构，因此这里自己简单用链表实现一个。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// -----双端队列实现 begin-------
// QueueNode 队列节点
type QueueNode struct {
Val int
Next *QueueNode
Pre *QueueNode
}
// DoubleQueue 双端队列
type DoubleQueue struct {
Left *QueueNode
Right *QueueNode
Size int
}
// LeftPeek 获取左端元素值
func (dq *DoubleQueue) LeftPeek() int {
return dq.Left.Val
}
// LeftPush 从左端插入新元素
func (dq *DoubleQueue) LeftPush(num int) {
node := new(QueueNode)
node.Val = num
if dq.Left == nil && dq.Right == nil {
dq.Left = node
dq.Right = node
} else {
current := dq.Left
current.Pre = node
node.Next = current
dq.Left = node
}
dq.Size++
}
// LeftPop 从左端弹出元素
func (dq *DoubleQueue) LeftPop() int {
current := dq.Left
dq.Left = current.Next
if dq.Left != nil {
dq.Left.Pre = nil
}
dq.Size--
if dq.Size == 0 {
dq.Right = nil
}
return current.Val
}
// RightPeek 获取右端元素值
func (dq *DoubleQueue) RightPeek() int {
return dq.Right.Val
}
// RightPush 从右端插入新元素
func (dq *DoubleQueue) RightPush(num int) {
node := new(QueueNode)
node.Val = num
if dq.Left == nil && dq.Right == nil {
dq.Left = node
dq.Right = node
} else {
current := dq.Right
current.Next = node
node.Pre = current
dq.Right = node
}
dq.Size++
}
// RightPop 从右端弹出元素
func (dq *DoubleQueue) RightPop() int {
current := dq.Right
dq.Right = current.Pre
if dq.Right != nil {
dq.Right.Next = nil
}
dq.Size--
if dq.Size == 0 {
dq.Left = nil
}
return current.Val
}
// -----双端队列实现 end-------
// -----题目解答 begin------
func maxSlidingWindow(nums []int, k int) []int {
length := len(nums)
res := []int{}
// 初始化一个双端队列，用于存储窗口内的最大值
dq := new(DoubleQueue)
left, right := 0, 0
for right < length {
rightNum := nums[right]
if dq.Size == 0 {
dq.RightPush(rightNum)
} else {
for dq.Size > 0 && rightNum > dq.RightPeek() {
dq.RightPop()
}
dq.RightPush(rightNum)
}
right++
if right-left == k {
res = append(res, dq.LeftPeek())
if dq.Size > 0 && nums[left] == dq.LeftPeek() {
dq.LeftPop()
}
left++
}
}
return res
}
// -----题目解答 end------
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK