Meta 固定窗口平均值：滚动总和与流式处理

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 只输出完整大小k窗口，k>n返回空列表，k<=0拒绝。输入数值可为负数；示例使用Python整数求和、浮点除法。
• “每个前缀最近k项”的流式moving average属于扩展，未满k时是否输出需要另行约定。

解题路线

1. 首窗口求和，之后每移动一步减去离开值、加入新值；sum始终等于当前窗口的k个元素之和。
2. 将原数组下标作为访问工具，额外状态只需总和。流式版本无原数组则用长度k队列，空间由O(1)变O(k)。
3. 若追问最大平均值，只维护最大sum；同一k下比较sum等价比较平均，避免不必要除法。浮点流可采用补偿求和或周期重算以控制累积误差。

手动走一遍

[1,−1,5,3]、k=2产生[0,2,4]；三次sum分别0/4/8。k=4只输出2；空输入或k大于长度输出[]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def window_averages(values, k):
    if k <= 0:
        raise ValueError("positive window required")
    if k > len(values):
        return []
    total = sum(values[:k])
    answer = [total / k]
    for right in range(k, len(values)):
        total += values[right] - values[right - k]
        answer.append(total / k)
    return answer

复杂度

O(n)时间，O(1)辅助空间，不包括O(n−k+1)结果。流式保存离开值需O(k)空间。

易错点与追问

容易失分的边界

• 把最大窗口平均值题的单个结果用于“所有平均值”会丢输出。
• 浮点sum在大量更新后可能漂移；若数值范围极大，明确精度与溢出要求。

继续深挖

• 多个不同k同时查询可预建前缀和，用prefix[i+k]−prefix[i]得每个窗口sum，但辅助空间O(n)。
• 滑动窗口中位数不能用一个总和维护；需要有序结构支持插入和删除。