滑动窗口Sliding window

维护连续窗口及其摘要，随着边界变化增量更新。

核心约束: 窗口统计与当前左右边界所覆盖元素一致。
适用问题: 连续子序列、流式聚合与局部条件匹配。
边界与取舍: 是否能单调收缩取决于问题条件，负数等可能破坏性质。

时间与空间#

n 为序列长度，w 为窗口长度或最大有效窗口大小。

时间成本: 边界单向推进、增删状态 $O(1)$ 时 $O(n)$
空间成本: 窗口和可 $O(1)$ ；频率表 / 单调队列可 $O(w)$

固定窗口可直接移入移出。可变窗口必须证明收缩条件的单调性；含负数时“和超限就缩左边”的常见规则可能失效。窗口中位数等操作可能每步 $O(\log w)$ 。

基础原理参考资料

USACO Guide · Sliding Window维护连续区间及左右边界的单调推进。