数据结构与算法 / 系统课时

滑动窗口处理连续区间

滑动窗口处理连续区间

滑动窗口用两个边界维护一个连续区间,并在边界移动时增量更新区间状态。本课将把固定长度与可变长度窗口放进同一套思路中,重点解决执行顺序、适用条件和答案更新时机三个易错点。

学习目标

  • 区分固定长度窗口与可变长度窗口
  • 掌握扩张、收缩和更新答案的正确顺序
  • 判断可变窗口是否具备所需的单调性

适用问题与判断条件

滑动窗口适合连续子数组或连续子串问题,例如固定长度区间最大和、满足约束的最短区间、至多包含若干种字符的最长子串。它的关键不是“使用两个指针”,而是窗口状态能否在元素加入和移出时高效更新。

固定长度窗口只需维持长度等于 k。可变长度窗口还要求约束随扩张或收缩呈稳定变化。例如数组元素全部为正数时,右端加入元素不会让区间和减小,左端移出元素不会让区间和增大,因此可以寻找“和至少为目标值的最短区间”。

固定窗口与可变窗口的移动过程

两类窗口的执行顺序

固定长度窗口的顺序是:加入右端元素,若窗口过长则移除左端元素,长度恰好为 k 时更新答案。每次移动只处理两个边界附近的元素。

寻找最短合法区间时,应在窗口合法期间记录答案并继续收缩;寻找最长合法区间时,通常先把非法窗口收缩到合法状态,再记录当前长度。需要连续收缩时必须使用 while,一次 if 可能留下仍不满足要求的窗口。

主示例

下面的程序同时演示固定窗口最大和,以及正整数数组中和至少为目标值的最短区间。第二个函数依赖“元素均为正数”这一前提。

python
from typing import Sequence

def max_sum_fixed_window(nums: Sequence[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k 必须位于 1 到数组长度之间")

    window_sum = sum(nums[:k])
    best = window_sum

    for right in range(k, len(nums)):
        # 加入新元素并移除离开窗口的旧元素
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum)

    return best

def min_length_at_least(nums: Sequence[int], target: int) -> int:
    if any(value <= 0 for value in nums):
        raise ValueError("该滑动窗口写法要求所有元素为正数")

    left = 0
    window_sum = 0
    best = len(nums) + 1

    for right, value in enumerate(nums):
        window_sum += value

        # 窗口合法时持续收缩,尝试得到更短答案
        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if best == len(nums) + 1 else best

def main() -> None:
    print(max_sum_fixed_window([2, 1, 5, 1, 3, 2], 3))
    print(min_length_at_least([2, 3, 1, 2, 4, 3], 7))

if __name__ == "__main__":
    main()

预期输出:

text
9
2

第一个答案来自区间 [5, 1, 3],第二个答案来自区间 [4, 3]。

边界与复杂度

闭区间 [left, right] 的长度是 right - left + 1,不要与左闭右开区间混用。窗口和、频次和不同元素数量通常可在常数时间更新;窗口最大值或最小值在旧元素移出后难以直接恢复,通常需要单调队列。

两个边界都只向右移动,因此时间复杂度为 O(n),额外空间取决于窗口状态。若数组包含负数,区间和不再具有上述单调性,简单可变窗口可能失效,应考虑前缀和或单调队列。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

滑动窗口处理连续区间

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通