跳到主要内容

滑动窗口模式

滑动窗口解决什么问题？​

  • 对象: 数组或字符串中的连续区间;
  • 目标: 在 O(n) 时间内统计满足条件的连续区间的性质 (长度、个数、最值);
  • 本质: 快慢指针的特殊形式, left 与 right 共同框出窗口;

固定长度窗口与不定长度窗口有什么区别？​

固定长度不定长度
窗口大小恒为 k由条件决定
扩张时机right 右移直到窗口满right 右移直到满足条件
收缩时机窗口满后同步右移 left条件被破坏时右移 left
典型问题定长子数组的平均值或统计最长无重复子串、最短覆盖子串

定长窗口的模板是什么？​

left = 0
right = 0
while right < len(nums):
    window.append(nums[right])
    if right - left + 1 >= window_size:
        维护答案
        window.popleft()
        left += 1
    right += 1

不定长窗口的模板是什么？​

left = 0
right = 0
while right < len(nums):
    window.append(nums[right])   # 扩张
    while 窗口需要收缩:
        window.popleft()         # 收缩
        left += 1
    right += 1
  • 每个元素最多被 right 加入一次、被 left 移出一次, 总复杂度 O(n);

维护答案时要注意什么？​

  • 只有窗口合法时才更新答案会漏掉最后一次收缩前的状态, 需要明确更新时机;
  • 求最短长度: 收缩前先更新答案, 再移动 left;
  • 求最长长度: 先收缩到合法, 再更新答案;
  • 无法找到答案时用哨兵值 (如 n + 1) 标记, 输出前再转换;