滑动窗口

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

滑动窗口主要通过 两个指针（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% 的滑动窗口问题！ 💪

Previous329. Longest Increasing Path in a MatrixNextPermutation in String

Last updated

Was this helpful?