reference：灵茶山艾府

定长滑窗

入：下标为i的元素进入窗口，更新相关统计量。如果i<k−1则重复第一步。

更新：更新答案。一般是更新最大值/最小值。

出：下标为i−k+1的元素离开窗口，更新相关统计量。

LC 1456 LC 1052 爱生气的书店老板：答案=所有不生气时间的客人数量+窗口内生气的客人数量

1297. 子串的最大出现次数✨

高频题，贪心思想

不定长滑窗

LC 2779

最短窗口

如果符合条件，while循环里先更新答案，并且pop左边

LC 219 模版题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    s,l=0,0
    res=inf
    for r, x in enumerate(nums):
        s+=x
        while s>=target:
            res=min(res, r-l+1)
            s-=nums[l]
            l+=1
    return res if res<inf else 0

🌟如果这题的条件改为 s==target 时才能更新答案，则这种方式有局限性，因为 target=0 时会有问题。

所以优先考虑以下写法：

1
2
3
4
5

while cur>target_r:
    cur-=nums[l]
    l+=1
if cur==target_r:
        res=min(res, i-l+1)

2904. 最短且字典序最小的美丽子字符串

while循环的作用：尽可能缩小答案的长度
字典序最小：直接比较两个字符串的大小

76. 最小覆盖子串🌟

最优解法

1234. 替换子串得到平衡字符串

正难则反

最长窗口

window里最多只能有两个不同元素/最多可以改变k个元素，求最长子串

先加右边。如果不符合条件，while循环不断pop左边，得到 valid子串，然后更新 res.

LC 2024
LC 2779
1658. 将 x 减到 0 的最小操作数 逆向思维
LC 3

与LC3 类似的问题：最少需要把字符串分成多少份，使得每一份都没有重复字母？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def soln(password: str) -> int:
    count = 1
    seen = set()

    for i in range(len(password)):
        c = password[i]
        if c in seen:
            seen = {c}
            count += 1
        else:
            seen.add(c)

    print(count)
    return count

1438. 绝对差不超过限制的最长连续子数组🌟

用两个队列专门存放当前窗口中的最大值和最小值.

最大值队列里面单调递减，因为遇到了新的更大的值，需要把之前的元素从队尾 pop

求子数组个数-越短越合法

713. 乘积小于 K 的子数组

求子数组个数-恰好型

930. 和相同的二元子数组

把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left 1和 left 2.
left 1 在左边，意思是正好符合条件。left 2 在右边，正好不符合条件。

424. 替换后的最长重复字符（高频）

给窗口内每个字符计数，每次获取到次数最多的字符出现的次数，
当前窗口长度-该次数=需要被替换的次数

992. K 个不同整数的子数组

可以转化为，atMostK(k)-atMostK(k-1)