1
class Solution:
2
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
3

4
        output = []
5
        q = deque()  # 存下标，队头始终是当前窗口最大值的下标
6
        l = r = 0
7

8
        while r < len(nums):
9

10
            # 只要队列不为空且新来的数比队尾大，队尾就没资格留了
11
            # （它没新数年轻，又没新数技术好）
12
            while q and nums[q[-1]] < nums[r]:
13
                q.pop()
14
            # 删完队尾后把 r 入队（如果上面 while 没触发，说明新数不如队尾大，直接跟在后面）
15
            q.append(r)
16

17
            # 如果队头已经滑出窗口左边界，过期了，直接移除
18
            if l > q[0]:
19
                q.popleft()
20

21
            # 窗口凑够 k 个后，队头就是当前最大值，记录并右移左边界
22
            if (r + 1) >= k:
23
                output.append(nums[q[0]])
24
                l += 1
25

26
            r += 1
27

28
        return output

1
class Solution:
2
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3
        """
4
        右指针一直往右走，每走一步就把 nums[r] 加进当前窗口的总和。
5
        一旦总和够了（≥ target）就开始从左边缩窗口——记当前长度，把左边的数减掉，左指针右移，看能不能缩得更短。
6
        一直缩到总和不够了为止，然后右指针继续往右走。
7
        """
8
        l, total = 0, 0
9
        # 还没找到答案时用无穷大占位
10
        res = float("inf")
11

12
        for r in range(len(nums)):
13
            # 对于每次右指针的移动，我们都要更新一遍当前窗口中数字的总和
14
            total += nums[r]
15
            # 只要当前窗口总和比 target 大（或者等于）的时候
16
            # 我们就缩小窗口，也就是左指针右移，看看能不能找到更短的满足条件的窗口
17
            # 为什么不右移右指针呢？因为我们要找尽可能小的窗口来满足 target
18
            # 往右移动右指针就是增加了我们窗口的长度了
19
            while total >= target:
20
                # 我们要记录当前窗口的长度，然后和之前记录的窗口长度做比较，谁小就选谁作为新的 res
21
                res = min(res, r - l + 1)
22
                # 我们移动左指针之前要先把左指针当前指向的数字从 total 里面减掉
23
                # 因为我们马上左指针要右移了，当前左指针指向的数字会掉出滑动窗口，必须先减掉
24
                total -= nums[l]
25
                l += 1
26

27
        return 0 if res == float("inf") else res

1
from collections import Counter
2
class Solution:
3
    def checkInclusion(self, s1: str, s2: str) -> bool:
4
        """
5
        滑动窗口：固定大小（len(s1)），每次右边加一个字符，左边移出一个字符，
6
        用 Counter 比较窗口内字符分布是否和 s1 一致。
7
        """
8
        # 如果 s1 = "ab" 那么 counterDict1 = {'a': 1, 'b': 1}
9
        counterDict1 = Counter(s1)
10
        # 初始化左指针为 0，右指针为 len(s1) - 1，构造定长的、长度等于 s1 长度的滑动窗口
11
        left = 0
12
        right = len(s1) - 1
13
        # 初始化时故意只统计 s2[0:right]，空出 right 位置
14
        # 因为 while 循环第一行会立即把 s2[right] 加进来，避免重复计数
15
        counterDict2 = Counter(s2[0:right])
16

17
        # 只要右指针没出界
18
        while right < len(s2):
19

20
            # 立马将右指针指向的字母添加到计数字典中，并且计数 +1
21
            counterDict2[s2[right]] += 1
22

23
            # 判断如果两个计数字典相等就返回 True
24
            if counterDict1 == counterDict2:
25
                return True
26
            # 如果不相等，先将左指针指向的字母计数 -1
27
            counterDict2[s2[left]] -= 1
28
            # 如果计数 -1 之后左指针指向的字母的计数直接为 0 了，那么在计数字典中删除左指针指向的字母
29
            # 也就是在字典中删除对应的键（{"a": 0} != {} 会导致误判）
30
            if counterDict2[s2[left]] == 0:
31
                del counterDict2[s2[left]]
32

33
            left += 1
34
            right += 1
35

36
        return False