image-20240519163601830

滑动窗口问题

滑动窗口主要解决子数组或者子串问题，其优点是可以避免暴力算法导致的O(n²)的时间复杂度，降低时间复杂度到O(n)。

滑动窗口的代码模板如下：

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
# 滑动窗口算法框架
def slidingWindow(s: str):
    # 用合适的数据结构记录窗口中的数据，根据具体场景变通
    # 比如说，我想记录窗口中元素出现的次数，就用 map
    # 我想记录窗口中的元素和，就用 int
    window = dict()
    
    left = 0
    right = 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        window[c] = window.get(c, 0) + 1
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        #...

        #/*** debug 输出的位置 ***/
        # 注意在最终的解法代码中不要 print
        # 因为 IO 操作很耗时，可能导致超时
        # print(f"window: [{left}, {right})")
        #/********************/

        # 判断左侧窗口是否要收缩
        while left < right and "window needs shrink":
            # d 是将移出窗口的字符
            d = s[left]
            window[d] -= 1
            if window[d] == 0:
                del window[d]
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            #...

滑动窗口需要关注的几个点：

练习题

76、最小覆盖子串

最小覆盖子串

题目条件

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
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window = defaultdict(int)
        need = defaultdict(int)
        for ch in t:
            need[ch] += 1

        left, right = 0, 0
        start, length = 0, float("inf")
        valid = 0
        while right < len(s):
            c = s[right]
            right += 1
            # window[c] += 1
            # print(window)
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            while valid == len(need):
                # 只有字符串字符串长度更短才会进行更新
                if right - left < length:
                    start, length = left, right - left
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        # print(window)
        return "" if length == float("inf") else s[start:start + length]


if __name__ == '__main__':
    s = "ADOBECODEBANC"
    t = "ABC"
    print(Solution().minWindow(s, t))

image-20240519145147478

3、无重复字符的最长子串

image-20240519155204142

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = 0
        left, right = 0, 0
        window = defaultdict(int)
        while right < len(s):
            c = s[right]
            right += 1
            window[c] += 1

            while window[c] > 1:
                d = s[left]
                left += 1
                window[d] -= 1
            length = max(length, right - left)
        return length

image-20240519155231234

567、字符串的排列

image-20240519160518124

题目中说s2是否包含s1的排列，实际上只需要判断s2和s1中相同字母的个数是否相等即可，这里通过2个字典window与need和一个valid进行维护。

  • window：窗口为当前的字符与其对应的个数
  • need：字符串s1的所有字符与其个数
  • valid：为window和need中是字符个数是否相等
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
from collections import defaultdict


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window, need = defaultdict(int), defaultdict(int)
        for ch in s1:
            need[ch] += 1
        left, right = 0, 0
        valid = 0
        while right < len(s2):
            c = s2[right]
            right += 1
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            while right - left >= len(s1):
                if valid == len(need):
                    return True
                d = s2[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return False


if __name__ == '__main__':
    s = Solution()
    print(s.checkInclusion(s1="ab", s2="eidbcaooo"))

image-20240519220402320

438、找到字符串中所有字母异位词

image-20240519161212003

整体思路与字符串排列相同，区别就在于需要找到所有的结果，只需要用一个列表进行接收即可。

其中第二个while循环是为了缩小窗口，获得最终正确的结果

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
from collections import defaultdict
from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window, need = defaultdict(int), defaultdict(int)
        left, right = 0, 0
        valid = 0
        res = []
        for ch in p:
            need[ch] += 1
        while right < len(s):
            c = s[right]
            right += 1
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            while right - left >= len(p):
                if valid == len(need):
                    res.append(left)
                d = s[left]
                window[d] -= 1
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res


if __name__ == '__main__':
    s = "cbaebabacd"
    p = "abc"
    print(Solution().findAnagrams(s, p))

image-20240519162616071

239、滑动窗口的最大值

滑动窗口的最大值

滑动窗口的最大值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
28
29
30
class Myqueue:
    def __init__(self):
        self.queue = deque()  # 单调队列 只记录窗口中的最大最小值

    def push(self, val):
        while self.queue and self.queue[-1] < val:
            self.queue.pop()
        self.queue.append(val)

    def pop(self, val):
        if self.queue and self.queue[0] == val:
            self.queue.popleft()

    def getMax(self):
        return self.queue[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        mq = Myqueue()
        res = []
        for i in range(k):
            mq.push(nums[i])
        # print(mq.queue)
        res.append(mq.getMax())
        for i in range(k, len(nums)):
            mq.pop(nums[i - k])
            mq.push(nums[i])
            res.append(mq.getMax())
        return res

1052、爱生气的书店老板

image-20240527210704040

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 maxSatisfied(
        self, customers: List[int], grumpy: List[int], minutes: int
    ) -> int:
        """
        :param customers:顾客数量
        :param grumpy: 生气
        :param minutes: 老板可以保持这个分钟数不生气
        :return:
        """
        res = 0
        for i in range(len(customers)):
            if grumpy[i] == 0:
                res += customers[i]
                customers[i] = 0
        # print(customers)
        # print(res)
        max_res = float("-inf")
        cur = 0
        left, right = 0, 0
        while right < len(customers):
            # if right - left < minutes:
            cur += customers[right]
            # print(queue)
            # queue.append(customers[right])
            right += 1
            if right - left > minutes:
                cur -= customers[left]
                left += 1
                # queue.popleft()
            max_res = max(max_res, cur)
        # print(max_res)
        return res + max_res

反过来的思路：求最大反过来求最小或者求最小反过来求最大

1423. 可获得的最大点数

最后的牌肯定连续，需要点数最大，则最后连续的牌值越小，过来求滑动窗口的最小值即可。

1052. 爱生气的书店老板

本题思路是求连续生气的中长度为minute的最大子数组之和。