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

处理定长与变长窗口差异

处理定长与变长窗口差异

滑动窗口最容易出错的地方,不是左右指针怎么写,而是什么时候收缩。本篇用一个统一判断框架区分定长窗口与变长窗口,并用两类典型题演示正确更新答案的时机。

学习目标

  • 根据题意判断窗口长度是固定还是由条件动态决定
  • 掌握两类窗口各自的扩张、收缩和答案更新顺序
  • 避免把 if、while 和更新答案的位置套错

先判断窗口受什么约束

定长窗口的核心约束是“窗口长度必须等于 k”。右端每加入一个元素,只要窗口超过 k,左端就必须同步移出一个元素,因此窗口大小始终围绕固定长度变化。

变长窗口没有固定大小,而是由某个条件控制,例如“区间和至少为 target”或“区间内不同字符不超过 k 个”。右端负责让窗口获得更多信息,左端负责在条件允许时尽量压缩。

定长窗口与变长窗口的收缩时机对比

一个实用判断是:题目如果直接给出“长度为 k 的子数组/子串”,优先考虑定长窗口;如果要求“满足条件的最短、最长区间”,通常需要变长窗口,但前提是窗口条件具有可维护的单调性。

两类窗口的代码骨架

下面把“长度为 k 的最大子数组和”和“和至少为 target 的最短子数组”放在同一个可运行示例中。第二个问题限定数组元素为正数,因为只有这样,右移右端不会让窗口和下降,左移左端也不会让窗口和上升。

python
def max_sum_fixed(nums, k):
    if k <= 0 or k > len(nums):
        return None

    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_len_at_least(nums, target):
    left = 0
    window_sum = 0
    best = len(nums) + 1

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

        # 条件成立后连续收缩,才能得到以 right 结尾的最短合法窗口。
        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


print(max_sum_fixed([2, 1, 5, 1, 3, 2], 3))
print(min_len_at_least([2, 3, 1, 2, 4, 3], 7))

预期输出

text
9
2

第一题的窗口长度一旦达到 k 就固定下来,每轮只需要“一进一出”;第二题则必须使用 while,因为同一个右端点可能对应多个合法窗口,只有持续移动左端,才能找到其中最短的那个。

更新答案的时机决定对错

定长窗口通常在“窗口刚好达到 k”时更新答案。若先更新再移出旧元素,就可能把长度为 k + 1 的非法窗口算进去。

变长窗口要看优化目标。求“最短合法区间”时,应在条件成立的 while 中先更新答案,再移出左端;求“最长合法区间”时,常见模式是先收缩到重新合法,再用当前窗口长度更新最大值。

先验证窗口不变量

写完代码后,优先检查三个不变量:定长窗口更新答案时长度是否恰好为 k;变长窗口进入 while 时条件是否真的成立;左端移出元素后,维护量是否同步更新。

如果条件不具备单调性,例如数组包含负数时用“区间和至少为目标值”做普通双指针,右端扩张与左端收缩都不能保证方向一致,此时就不应强行使用标准滑动窗口。

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

目录与阅读设置

阅读设置

17

记录一个想法

处理定长与变长窗口差异

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

登录哪都通