LeetCode LCR 041. 数据流中的移动平均值

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 041. 数据流中的移动平均值

题意分析

题目目标：构造时给定一个固定窗口宽度 size，此后每次 next(val) 把 val 追加进数据流，并返回数据流末尾最多 size 个数字的算术平均值，返回类型是浮点数。
核心约束：窗口宽度构造之后不再变化，这说明所需内存是常量级的；next 会被反复调用（调用次数远大于 size），因此单次调用的代价必须与 size 无关，否则总代价会退化成两个规模的乘积。
边界处理：调用次数还不足 size 时，分母是"已经来过的数字个数"而不是 size；size 等于 1 时每次返回的就是 val 本身；元素允许为负数，求和不能假设单调；求平均必须走浮点除法，整数除法会截断。
实现取舍：只需要"最近 size 个"这一段后缀，早于它的数字永远不会再参与任何一次计算，所以数据流可以只保留一个固定长度的缓冲区，而不必留下全部历史。

解法：数组扫描

核心思路

最直接的做法是把所有来过的数字都存进一个可变长数组，每次 next 时从末尾往前取 size 个重新累加再除以个数。这样能过，但每次调用都要重新加一遍窗口里的所有数字，m 次调用的总代价是 $O(m \cdot size)$，而且内存随调用次数无限增长。
瓶颈在于重复劳动：第 i 次和第 i+1 次调用的窗口高度重合，只在两端各差一个元素——右边进来一个新数字，左边挤出一个最老的数字。既然差异只有两项，和就没有必要重算，用加减修正即可。
由此确定要维护的两条不变量：其一，s 恒等于当前窗口内全部元素之和；其二，缓冲区 arr 的长度恒为 size，下标 cnt % size 处存放的恰好是"下一次将被挤出窗口的那个元素"（窗口尚未填满时该位置是初始值 0，减 0 不改变和，与"没有元素被挤出"语义一致）。
有了这两条，next 只做三件事：s += val - arr[idx] 完成一进一出的修正，arr[idx] = val 让缓冲区继续满足不变量二，cnt 自增记录总数。分母取 min(cnt, size)，因为真实窗口宽度是"已到达个数"与"窗口上限"中的较小者。

解题步骤

构造函数里开一个长度为 size 的整型数组 arr，并把和 s、计数 cnt 初始化为 0。为什么用定长数组而不是链式结构：窗口宽度已知且固定，定长数组配合取模就能天然实现"新值覆盖最老值"，省掉了节点分配与指针维护。

每次 next 先算出本次写入位置 idx = cnt % arr.length。为什么这个位置正好是最老元素：cnt 是此前已写入的总数，写入是按 0,1,2,... 循环推进的，所以下标 cnt % size 上残留的是 size 次之前写下的那个值，也就是当前窗口左端之外的第一个元素。

用 s += val - arr[idx] 一次完成"减去出窗元素、加上入窗元素"。为什么要先减后写：arr[idx] 在被覆盖之前才是旧值，顺序颠倒就拿不到需要扣除的那一项了。

再执行 arr[idx] = val 与 ++cnt。为什么 cnt 只增不取模：它同时承担"总到达个数"的职责，取模会丢掉窗口未满阶段判断分母所需的信息。

返回 s * 1.0 / Math.min(cnt, arr.length)。为什么要乘 1.0：s 与分母都是整型，不做提升就会先执行整数除法把小数部分截掉。

以 具体用例：size = 3，依次调用 next(1)、next(10)、next(3)、next(5) 走一遍。初始 arr = [0,0,0]，s = 0，cnt = 0。第一次 val = 1，idx = 0，s = 0 + 1 - 0 = 1，arr = [1,0,0]，cnt = 1，分母 min(1,3) = 1，返回 1.0。第二次 val = 10，idx = 1，s = 1 + 10 - 0 = 11，arr = [1,10,0]，cnt = 2，分母 2，返回 5.5。第三次 val = 3，idx = 2，s = 11 + 3 - 0 = 14，arr = [1,10,3]，cnt = 3，分母 3，返回 14 / 3 ≈ 4.666...。第四次 val = 5，idx = 3 % 3 = 0，此时 arr[0] = 1 正是要挤出窗口的最老元素，s = 14 + 5 - 1 = 18，arr = [5,10,3]，cnt = 4，分母 min(4,3) = 3，返回 6.0，与直接计算 (10+3+5)/3 完全一致。

代码实现

// 核心实现：数组扫描，维护必要状态并避免重复处理。
class MovingAverage {
    private int[] arr;
    private int s;
    private int cnt;

    public MovingAverage(int size) {
        arr = new int[size];
    }

    public double next(int val) {
        int idx = cnt % arr.length;
        s += val - arr[idx];
        arr[idx] = val;
        ++cnt;
        return s * 1.0 / Math.min(cnt, arr.length);
    }
}

// 核心实现：数组扫描，维护必要状态并避免重复处理。
type MovingAverage struct {
    arr []int
    cnt int
    s   int
}

func Constructor(size int) MovingAverage {
    arr := make([]int, size)
    return MovingAverage{arr, 0, 0}
}

func (this *MovingAverage) Next(val int) float64 {
    idx := this.cnt % len(this.arr)
    this.s += val - this.arr[idx]
    this.arr[idx] = val
    this.cnt++
    return float64(this.s) / float64(min(this.cnt, len(this.arr)))
}

复杂度分析

时间复杂度：构造 $O(size)$，单次 next 为 $O(1)$。凭什么：next 内部只有一次取模、一次加减、一次赋值和一次除法，全是常数条指令，与窗口宽度和已到达元素个数都无关。

空间复杂度：$O(size)$。凭什么：除了固定长度为 size 的缓冲区外，只额外保存了和与计数两个标量，历史数据不做任何留存。

关键点总结

窗口只在两端变化时，和应当用"加新值、减旧值"增量维护，而不是每次重算，这是所有定宽窗口统计量（和、平均、计数）的通用套路。

定长数组加下标取模，就是一个不需要搬移元素的先进先出缓冲区；只要窗口宽度提前已知，它比链式结构更省事也更快。

数组初始值 0 在这里不是"脏数据"而是合法状态：窗口未满时减 0 恰好等价于"没有元素出窗"，让填充期和稳定期共用同一段代码。

计数器同时充当"写入位置来源"和"分母判据"两种角色，所以必须保留原始累计值而不能提前取模。

面试视角：面试官问这题时真正想听的是"能不能把单次查询压到 $O(1)$、把内存压到 $O(size)$"。先说暴力的 $O(m \cdot size)$ 与无限增长的内存，再点出"相邻窗口只差两个元素"这一观察，最后主动补一句"如果窗口宽度会动态变化，就换成双端队列存下标"，通常就能收住这道题。

易错点总结

错误写法：把 arr[idx] = val 写在 s += val - arr[idx] 之前 → size = 3 时依次输入 1,10,3,5，第四次读到的 arr[0] 已被改成 5，和变成 14 + 5 - 5 = 14，返回 4.666 而不是正确的 6.0。

错误写法：分母直接写死 arr.length → size = 3 只调用一次 next(1)，返回 0.333 而不是 1.0，窗口未填满阶段的答案全错。

错误写法：return s / Math.min(cnt, arr.length) 漏掉浮点提升 → size = 3 输入 1,10,3 时整数除法得到 3，返回 3.0 而不是 4.666，小数部分被静默截断。

错误写法：给 cnt 也取模，写成 cnt = (cnt + 1) % arr.length → size = 3 输入四个数后 cnt 归零，min(cnt, size) 变成 0，直接除零得到 Infinity 或 NaN。

错误写法：把总和声明为窗口内元素的最大绝对值可能溢出的类型，或者在别的变种里用 int 累加 size 个 $10^9$ 级别的数 → 例如窗口宽 $10^5$、每个值 $10^5$，和达到 $10^{10}$ 超出 32 位范围，平均值变成负数。

错误写法：改用 List 存全部历史再取末尾 size 个求和 → 调用 $10^5$ 次、size 为 $10^4$ 时要做 $10^9$ 次加法，直接超时，同时内存随调用次数线性增长。

错误写法：构造函数里没有真正分配数组（Go 中写成 var arr []int 而不是 make([]int, size)）→ 第一次 next 执行 cnt % len(arr) 就是对 0 取模，运行时 panic。

错误写法：为了"省事"在 next 里重新遍历 arr 求和 → size = 3 且只调用两次时，arr 中第三个位置的 0 也被算进去，返回 (1+10+0)/2 这样的错误值，同时把单次代价拖回 $O(size)$。

相似题目

题目	难度	考察点
933. 最近的请求次数	简单	窗口由时间戳而非个数界定，出窗条件变成比较时间差
362. 敲击计数器	中等	同一时刻可能多次敲击，需要按秒聚合后再做环形覆盖
622. 设计循环队列	中等	同样用定长数组取模，但要额外区分队空与队满
239. 滑动窗口最大值	困难	统计量换成最大值后无法增量加减，必须靠单调结构维护
295. 数据流的中位数	困难	数据流无窗口上限，中位数要靠两个堆对顶维护