滑动窗口技术 — 完整指南 (DSA)

Source: Dev.to

什么是滑动窗口技术？

滑动窗口是一种算法技巧，用于在数组或字符串中高效处理连续子数组或子串（大小固定或可变）。
与其为每个子数组重新计算值，窗口在向前移动时会复用之前的计算结果。

• 窗口大小 (k) – 一次检查的元素数量。
• 窗口 – 当前正在处理的元素组。

固定大小窗口示例

数组: [1, 3, -1, -3, 5, 3, 6, 7] k = 3

[1, 3, -1]
   [3, -1, -3]
      [-1, -3, 5]
         [-3, 5, 3]
            [5, 3, 6]
               [3, 6, 7]

对于每个窗口，我们可以在不再次遍历整个窗口的情况下计算某个属性（例如最大值）。

结果（每个窗口的最大值）： [3, 3, 5, 5, 6, 7]

滑动窗口的工作原理

1. 处理第一个窗口（索引 0 … k‑1）。
2. 对于每个后续索引 i = k … n‑1
   • 移除 离开窗口的元素（i‑k）。
   • 添加 新元素（i）。
   • 仅使用已更改的元素 更新答案。

这将朴素的 O(n·k) 工作量降低到 O(n)。

示例：大小为 k 的最大和子数组

// Time: O(n)   Space: O(1)
function maxSumSubarray(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  // first window
  for (let i = 0; i = k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

可变大小窗口（双指针）技术

当窗口大小事先未知时，我们向右扩展指针，直到某个条件不再满足，然后从左侧收缩窗口。

// Example: Length of the longest substring without repeating characters
function longestUnique(s) {
  const set = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

通用模式

left = 0
for right in range(0, n):
    扩大窗口（包含右侧元素）

    while 窗口不满足条件:
        缩小窗口（排除左侧元素）
        left += 1

    根据当前窗口更新答案

常见应用

典型的实际场景：

• 最近5分钟的峰值带宽使用。
• 最近30天的最高价格。
• 最近10次读取的平均温度。
• 检测最近N次请求中的异常。

为什么滑动窗口的时间复杂度是 O(n)

该技术本质上是一种 专门的双指针方法：

• 右指针始终向前移动，扩大窗口。
• 左指针仅在当前窗口违反条件时才向前移动。

因为每个元素至多被加入窗口一次、移出窗口一次，整体工作量随输入规模线性增长。

常见陷阱

• 忘记在窗口滑动时移除最左侧的元素。
• 使用朴素的嵌套循环，每次重新计算整个窗口（导致 O(n·k)）。
• 认为固定大小的解法（deque）适用于可变大小的问题；它们需要使用双指针的收缩‑扩张方法。

摘要

滑动窗口技术通过 重用先前的计算 并 仅维护必要的状态，在窗口遍历数据时，将许多子数组/子序列问题从二次时间转化为线性时间。无论窗口大小是固定的（使用 deque）还是可变的（使用 two pointers），核心思想保持不变：每个元素最多处理两次——一次在它进入窗口时，另一次在它离开窗口时。