30 核心算法：EP-05：滑动窗口算法

Source: Dev.to

为什么滑动窗口算法实际上是关于随时间保持上下文

许多系统的失败并不是因为缺乏信息。
它们的失败在于不断忘记刚刚发生的事情。

滑动窗口的存在就是为了解决这个问题。
它并不是为了优化循环或固定大小的子数组。
它是为了在系统前进的过程中保持相关上下文。

忘记过多的代价

考虑一个系统在序列上反复评估某个条件。
一种朴素的方法是每次都从头重新计算。每一步都重新开始，忽略了大部分上下文并未改变的事实。

这种方法是可行的，但却非常浪费。当输入逐渐变化时，重新计算会破坏连续性。系统不断再次回答相同的问题，每次都付出全部代价。虽然进展仍在发生，但记忆却丢失了。

Sliding Window：向前携带上下文

Sliding Window 改变了工作单元。它不再从零重新计算，而是询问：

“自上一步以来有什么变化？”

• 一个元素进入窗口。
• 一个元素离开。
• 其他保持不变。

该算法仅保留足够的状态以保持决策的准确性——而不需要携带完整的历史。这不是靠聪明的技巧进行的优化，而是通过克制实现的优化。

核心机制

initialize window state

for each new element:
    add new element to window
    while window violates constraint:
        remove old element from window
    evaluate window

细节可能各不相同，但原则不变。状态是增量更新的；除非必须，否则不会重新计算。

为什么滑动窗口依赖时间

滑动窗口假设一个基本前提：顺序很重要。
窗口只向前移动，永不后退。决策基于最近的信息，而非全局知识。

正因如此，该技术自然适用于以下问题：

• 流数据
• 时间序列数据
• 速率限制
• 滚动平均
• 有界历史

当时间单向流动时，滑动窗口不可避免。

滑动窗口作为稳定机制

大多数滑动窗口问题并不是在寻找某些东西；它们是关于在移动边界上保持条件稳定：

• 必须保持在范围内的最大值。
• 不能超过限制的频率。
• 必须保持在可接受范围的延迟。

当安全时窗口会扩展， 当不安全时会收缩。 这种持续的调整可以防止突发的峰值和静默漂移。

Fixed vs Variable Windows Isn’t the Point

固定大小窗口和可变大小窗口常被教学为不同的模式，但它们本质上是相同的思路，只是约束不同。

• 固定窗口假设通过大小来保证稳定性。
• 可变窗口假设必须动态强制稳定性。

在这两种情况下，窗口的作用都是在系统前进时保护上下文不丢失。

滑动窗口失效的情况

滑动窗口依赖于局部性：最近的信息必须比遥远的信息更相关。如果这一假设失效，窗口就失去意义。

该技术在以下情况下会遇到困难：

• 需要全局历史的任务。
• 非线性依赖。
• 依赖遥远过去状态的条件。

滑动窗口不会悄然失效；它只是变得不再适用。

它明确的权衡

Sliding Window 在完整性与连续性之间进行权衡。它并不记住所有内容，也不探索所有可能性。它只关注 最近相关 的内容。这个权衡是有意为之。在时间至关重要的系统中，遗忘不是错误——而是需求。

要点

滑动窗口算法并不是关于子数组或指针技巧。它的存在是为了在时间向前推进时保留恰当的上下文——防止重复计算，稳定决策，并保持系统响应而不失去准确性。这个理念在数据持续到达的各个场景中都会出现，这也是滑动窗口仍然是核心技术，而不仅仅是编码捷径的原因。