滑动窗口

发表于   |   更新于 | 分类于

1.前言

滑动窗口用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

2. 两种形式

  • 非固定长度窗口—快慢指针；如满足某一条件的子数组的最大最小长度。
  • 固定长度窗口—双端队列；如满足固定长度、某一条件的子数组中的最大最小值。

3. 非固定长度窗口

3.1 解题框架

1
2
3
4
5
6
7
8
9
10
11
left = 0
right = 0

window = []
while right < len(s):
	window.append(s[right])
  right += 1
  
  while (windon needs shrink):
    window.pop(0)
    left += 1

3.2 长度最小的子数组

leetcode:209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

1
2
3
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums: return 0

        left = 0
        right = 0
        
        summation = 0
        res = len(nums) + 1
       
        while right < len(nums):
            summation += nums[right]
            right += 1

            while summation >= s:
                res = min(res, right-left)
                summation -= nums[left]
                left += 1
 
        return res if res != len(nums)+1 else 0

3.2 无重复字符的最长子串

Leetcode:3 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        res = 0

        char2count = {}
        while right < len(s):
            char = s[right]
            right += 1
            if char not in char2count:
                char2count[char] = 0
            char2count[char] += 1

            while char2count[char] > 1:
                new_char = s[left]
                char2count[new_char] -= 1
                left += 1
            res = max(res, right-left)
        
        return res

3.3 最大连续1的个数 III

Leetcode 1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

1
2
3
4
5
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释： 
[1,1,1,0,0,**1**,1,1,1,1,**1**]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        right = 0

        res = 0
        while right < len(A):
            if A[right] == 0:
                K -= 1
            right += 1

            while K < 0:
                if A[left] == 0:
                    K += 1
                left += 1
            
            res = max(res, right-left)
        
        return res

3.4 最小覆盖子串

Leetcode: 76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

1
2
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 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
36
37
38
39
40
41
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict

        def helper(needs, windows):
            for key, value in needs.items():
                if windows[key] < value:
                    return False
            return True
        
        needs = defaultdict(int)
        windows = defaultdict(int)
        for char in t:
            needs[char] += 1
            windows[char] = 0
        
        left = 0
        right = 0
        start = 0

        res = len(s) + 1

        while right < len(s):
            char = s[right]
            right += 1

            if char in windows:
                windows[char] += 1
            

            while helper(needs, windows):
                if right-left < res:
                    start = left
                    res = right-left
                
                char = s[left]
                if char in windows:
                    windows[char] -= 1
                left += 1

        return '' if res == len(s) + 1 else s[start:start+res]
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
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:

        from collections import defaultdict

        def check(needs, windows):
            for key, value in needs.items():
                if windows[key] != value:
                    return False
            return True

        needs = defaultdict(int)
        windows = defaultdict(int)

        for char in p:
            needs[char] += 1
            windows[char] = 0

        left = 0 
        right = 0
        res = []

        while right < len(s):
            char = s[right]
            if char in windows:
                windows[char] += 1
            right += 1

            while right - left == len(p):
                if check(needs, windows):
                    res.append(left)
                char = s[left]
                if char in windows:
                    windows[char] -= 1
                left += 1
        return res

3.5 至多包含两个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t 。

1
2
3
输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。
1
2
3
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。
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 lengthOfLongestSubstring(self, s: str) -> int:
        count = 0
        char2count = {}
        left = 0
        right = 0
        res = 0 
      
        while right < len(s):
            char = s[right]
            right += 1
            if char not in char2count:
                char2count[char] = 0
            char2count[char] += 1
            if char2count[char] == 1:
                count += 1
            
            while count > 2:
                char = s[left]
                char2count[char] -= 1
                if char2count[char] == 0:
                    count -= 1
                left += 1
                
            res = max(res, right-left)
        return res

3.6 字符串的排列

Leetcode: 567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

1
2
3
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
1
2
输入: s1= "ab" s2 = "eidboaoo"
输出: False
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
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import defaultdict

        def check(needs, windows):
            for key,value in needs.items():
                if value != windows[key]:
                    return False
            return True

        needs = defaultdict(int)
        windows = defaultdict(int)     
        res = True

        for c in s1:
            needs[c] += 1
            windows[c] = 0

        left = 0
        right = 0

        while right < len(s2):
            char = s2[right]
            right += 1
            windows[char] += 1
            
            while right-left == len(s1):
                if check(needs, windows):
                    return True
                char = s2[left]
                windows[char] -= 1
                left += 1
        return False

3.7 串联所有单词的子串

Leetcode 30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

1
2
3
4
5
6
7
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
1
2
3
4
输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]
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
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter

        if not words or not s: return []
        
        one_word = len(words[0])
        word_num = len(words)

        n = len(s)
        words = Counter(words)
        res = []

        for i in range(0, one_word):
            cur_count = 0
            left = i
            right = i
            cur_Counter = Counter()
            while right + one_word <= n:
                w = s[right:right + one_word]
                right += one_word
                if w not in words:
                    left = right
                    cur_Counter.clear()
                    cur_count = 0
                else:
                    cur_Counter[w] += 1
                    cur_count += 1
                    while cur_Counter[w] > words[w]:
                        left_w = s[left:left+one_word]
                        left += one_word
                        cur_Counter[left_w] -= 1
                        cur_count -= 1
                    if cur_count == word_num:
                        res.append(left)
        return res

3.8 最小区间

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

1
2
3
4
5
6
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
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
class Solution(object):
    def smallestRange(self, nums: List[List[int]]): -> List[int]
        from collections import defaultdict

        v  = list()
        for i in range(len(nums)):
            for num in nums[i]:
                v.append((num, i))
        v.sort()

        left, right, n = 0, 0, len(v)
        index2count = collections.defaultdict(int)
        k = len(nums)
        count = 0
        res = [0, 0]
        diff = float('inf')

        while right < n:
            index = v[right][1]
            if index2count[index] == 0:
                count += 1
            index2count[index] += 1
            right += 1

            while count == k:
                if v[right][0] - v[left][0] < diff:
                    diff = v[right][0] - v[left][0]
                    res = [v[left][0], v[right][0]]
                d[v[left][1]] -= 1

                if d[v[left][1]] == 0:
                    count -= 1
                left += 1
        return res

4. 固定窗口

4.1 滑动窗口最大值

239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[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
类似于单调队列的思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      
        from collections import deque

        queue = deque()  

        # init queue
        for i in range(k):
            while queue and nums[queue[-1]] <= nums[i]: queue.pop()
            queue.append(i)
        
        res = [nums[queue[0]]]
        # slide the window
        for i in range(k, len(nums)):
            # remove the start of the window
            while queue and i - queue[0] + 1 > k:
                queue.popleft()

            while queue and nums[queue[-1]] <= nums[i]: queue.pop()
            queue.append(i)
            
            res.append(nums[queue[0]])
        return res
Donate comment here