数据结构与算法 / 系统课时
滑动窗口处理连续区间
滑动窗口处理连续区间
滑动窗口用两个边界维护一个连续区间,并在边界移动时增量更新区间状态。本课将把固定长度与可变长度窗口放进同一套思路中,重点解决执行顺序、适用条件和答案更新时机三个易错点。
学习目标
- 区分固定长度窗口与可变长度窗口
- 掌握扩张、收缩和更新答案的正确顺序
- 判断可变窗口是否具备所需的单调性
适用问题与判断条件
滑动窗口适合连续子数组或连续子串问题,例如固定长度区间最大和、满足约束的最短区间、至多包含若干种字符的最长子串。它的关键不是“使用两个指针”,而是窗口状态能否在元素加入和移出时高效更新。
固定长度窗口只需维持长度等于 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),额外空间取决于窗口状态。若数组包含负数,区间和不再具有上述单调性,简单可变窗口可能失效,应考虑前缀和或单调队列。
按自己的节奏,确认真正理解。