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

约 4 分钟
文章信息 2 个分类 4 个标签
分类
LeetCode 简单
标签
数组 设计 队列 数据流

题目描述

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

题意分析

固定一个窗口容量 size，每次接收到新整数时，返回最近至多 size 个输入值的平均数。窗口满后要排除最早进入的数；未满时只对已经收到的数求平均，不能把尚未填入的数据当作零参与分母。

调用会持续进行，需要在对象中保留最近数据和相关状态。平均数可能带小数，返回值应按浮点除法计算。当前题型约定容量为正，第一次调用后窗口就至少有一个有效元素。

解法：环形数组与滚动和

核心思路

[!blue]

平均数等于窗口总和除以有效数量，所以每次无需重新扫描全部窗口，只需维护滚动和 sum。加入新值时，把不再属于窗口的最老值扣掉，再加上新值，就能得到更新后的总和。

用固定长度数组保存最近的数据，head 指向下一次要写入的槽位。窗口未满时它指向尚未使用的零值槽；满了以后它就指向最早写入、即将被淘汰的元素。写入后令 head = (head + 1) % size，到数组末尾会回到开头，按输入先后顺序循环覆盖。

因此一次更新可以统一写成“总和加新值减该槽旧值，再覆盖该槽”。未满时旧槽为初始零，减去它不影响真实总和；满了以后减去的正好是最老元素。读取旧值必须在覆盖之前完成，否则会把新值误当作需要淘汰的值。

另用 count 保存当前有效数量，每收到一个数就增加，但达到容量后不再增加。数组的物理长度始终为 size，实际分母却应为 count，这样未填满阶段的平均值也正确。

最后先把总和转成浮点数，再除以有效数量。窗口和使用宽整数保存，避免先用较窄整数完成累计或差值计算；这一转换与环形数组位置管理分别解决数值与数据保留的问题。

解题步骤

  1. 构造时创建长度为 size 的全零数组，将写入位置、有效数量和总和都初始化为零。
  2. 收到新值后，先从总和扣除 values[head]，再加上新值。
  3. 把新值写入该槽，将写入位置循环推进一格。
  4. 窗口未满时增加 count，满了以后保持容量大小。
  5. 返回浮点总和除以 count 的结果。

代码实现

class MovingAverage {
    private final int[] values;
    private int head;
    private int count;
    private long sum;

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

    public double next(int val) {
        sum += (long) val - values[head];
        values[head] = val;
        head = (head + 1) % values.length;

        if (count < values.length) {
            count++;
        }

        return (double) sum / count;
    }
}

type MovingAverage struct {
    values      []int
    head, count int
    sum         int64
}

func Constructor(size int) MovingAverage { return MovingAverage{values: make([]int, size)} }

func (m *MovingAverage) Next(val int) float64 {
    m.sum += int64(val) - int64(m.values[m.head])
    m.values[m.head] = val
    m.head = (m.head + 1) % len(m.values)
    if m.count < len(m.values) {
        m.count++
    }
    return float64(m.sum) / float64(m.count)
}

复杂度分析

  • 时间复杂度：构造固定数组为 O(size)；每次 next 只读写一个槽位并更新几个变量，为 O(1)。
  • 空间复杂度：O(size)。只保留最近窗口需要的固定数量槽位，不随数据流总长度增长。

关键点总结

[!green]

  • 环形数组按先入先出次序覆盖，写入指针定位当前要淘汰的最老数据。
  • 滚动和只增新值、减旧值，不必重新累加整个窗口。
  • head 决定写入位置，count 决定有效分母，两者含义不同。
  • 先读取旧值再覆盖，先转浮点再除法。

易错点总结

[!yellow]

  • 窗口未满时直接除以容量：会把不存在的数据当成零加入平均，应除以实际数量。
  • 覆盖槽位后才扣除旧值：旧值已经丢失，滚动和会计算错误。
  • 忘记扣掉被覆盖的数：总和会变成整个历史数据流之和，而不是当前窗口和。
  • 写入下标不回绕：达到容量后会越界，需要循环推进。
  • 整数相除后再转浮点：小数部分已经丢失，类型转换应先于除法。
  • 让 count 无限增加：窗口最多保留容量个数，满了以后分母必须固定。

相似题目

题目 难度 关联与区别
933. 最近的请求次数 简单 同样移除不再属于窗口的旧数据，但窗口由时间戳界定，而非固定元素数量。
622. 设计循环队列 中等 复用环形数组下标回绕；本题额外维护窗口和，并允许新值覆盖最老值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/38513101
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！