滑动窗口

🚀 滑动窗口解题通用思路总结

滑动窗口主要通过 两个指针（left 和 right） 控制窗口的大小，动态维护窗口内的数据，使其符合题目的要求。一般可以归纳为以下几类思路：

---

🟢 1. 固定大小的滑动窗口

特点：窗口大小始终为 k，右指针 right 逐步向右扩展，左指针 left 也同步推进以维持窗口大小。

📌 解题模板：

for right in range(len(nums)):
    # 加入右侧元素
    # 维护窗口（如加入到单调队列、哈希表等）
    
    if right >= k - 1:  # 只有窗口大小达到 k 时才开始处理
        # 计算当前窗口的答案（如最大值/最小值）
        
        # 维护窗口（移除左边元素，使窗口保持大小 k）

📌 题目示例：

• 239. 滑动窗口最大值（双端队列）

• 567. 字符串的排列（哈希表匹配）

📌 核心技巧：

• 单调队列（deque）：保证 O(1) 查询最大/最小值

• 哈希表：统计窗口内字符频率进行匹配

• 堆：维护窗口内最大/最小值（不常用）

✅ 窗口右移的关键点：

• 右指针 right 每次右移一步

• 左指针 left 只有当 right - left + 1 > k 时才右移

---

🟡 2. 可变大小的滑动窗口

特点：窗口的大小不固定，而是根据题目条件动态调整，右边扩展窗口，左边收缩窗口。

📌 解题模板：

left = 0
for right in range(len(nums)):
    # 加入右侧元素，增加窗口大小
    
    while 窗口不符合条件:
        # 移动左指针收缩窗口，使窗口重新满足题目要求
        left += 1
    
    # 处理窗口答案（如果当前窗口符合要求）

📌 题目示例：

• 209. 长度最小的子数组（窗口内元素和 ≥ target）

• 713. 乘积小于 K 的子数组（窗口内乘积 < k）

• 3. 无重复字符的最长子串（窗口内不能有重复字符）

📌 核心技巧：

• 窗口扩展：right 指针总是右移，尝试加入新元素

• 窗口收缩：如果窗口不符合条件，left 指针向右移动，减少窗口大小

• 窗口内的数据结构：可使用 哈希表（判断字符是否重复），或 乘积/和等累积值 进行判断

✅ 窗口收缩的关键点：

• 满足约束时计算答案

• 不满足约束时 left 右移收缩窗口

---

🟣 3. 双指针 + 计数（特殊情况）

特点：有些题目不能严格使用 while 语句收缩窗口，而是需要更精细的控制 元素进入 & 移出窗口的方式。

📌 解题模板：

seen = {}
left = 0
for right in range(len(nums)):
    # 处理窗口内数据（如更新哈希表）
    
    while 窗口不合法:
        # 移除左侧元素
        left += 1
    
    # 计算当前窗口的答案

📌 题目示例：

• 567. 字符串的排列（匹配窗口内字符频率）

• 3. 无重复字符的最长子串（哈希表判断是否重复）

✅ 适用场景：

• 哈希表存储窗口内元素频次

• 字符/数字类问题，窗口内元素不能重复

• 窗口内元素需严格匹配某个模式

---

🔵 4. 乘积 / 乘法约束的滑动窗口

特点：窗口的判断条件是 乘积/商，而不是简单的 和/最大最小值。

📌 解题模板：

left = 0
prod = 1
for right in range(len(nums)):
    prod *= nums[right]
    
    while prod >= k and left <= right:
        prod /= nums[left]
        left += 1
    
    # 记录答案（窗口长度为 right - left + 1）

📌 题目示例：

• 713. 乘积小于 K 的子数组

✅ 关键技巧：

• 乘积过大时，左指针 left 右移以缩小窗口

• 每次 right 移动时，窗口的所有子数组数量为 right - left + 1

---

🔶 5. Deque (单调队列) 优化

特点：用于 滑动窗口最大值/最小值 类型问题，使用 双端队列 来保证 O(1) 查询窗口内最大/最小值。

📌 核心操作：

1. 维护队列的单调性（递减队列存储最大值，递增队列存储最小值）

2. 移除窗口外的元素

3. 保证队列头部 always 是最大/最小值

📌 代码示例：

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    res = []
    
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        
        if dq[0] <= i - k:
            dq.popleft()
        
        if i >= k - 1:
            res.append(nums[dq[0]])
    
    return res

✅ 时间复杂度：O(N) ✅ 空间复杂度：O(k)

---

🚀 归纳总结

类型	适用场景	关键技巧	示例题目
固定大小窗口	k 固定，求最大/最小	单调队列（deque）、哈希表	滑动窗口最大值 (LC 239)
可变大小窗口	找最长/最短子数组	right 右移扩展，left 收缩	长度最小子数组 (LC 209)
哈希表 + 滑动窗口	需要存储窗口内字符	维护 dict 记录字符频率	无重复字符最长子串 (LC 3)
窗口内乘积/商约束	乘积/商小于某值	维护 prod 乘积	乘积小于 K (LC 713)
Deque 单调队列	窗口内最大/最小值	递增/递减队列，O(1) 查询	滑动窗口最大值 (LC 239)

---

💡 总结

1. 窗口的右边 right 始终向右滑动

2. 窗口的左边 left 根据条件收缩

3. 判断窗口是否合法的条件：

   • 固定窗口大小 right - left + 1 == k

   • 求最优解（最大/最小/乘积等）

   • 满足某些约束条件（如 sum ≥ target）

4. 优化技巧：

   • 使用 Deque 维护窗口内最大/最小值

   • 使用 哈希表 记录窗口内字符频率

   • 使用 乘积变量 prod 处理乘法约束问题

🚀 记住这几个思路，你就能轻松解决 90% 的滑动窗口问题！ 💪