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

2026-03-28 HGNULB 约 4 分钟

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

分类

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

标签

数组 LCR 设计 队列 数据流

题目描述

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

题意分析

构造时给定正窗口大小 size，每次加入一个整数后，返回最近至多 size 个数的平均值。数据还不足 size 个时，全部已到达数据都参与计算，分母使用实际个数。

相邻两次窗口只相差新加入的数和可能被淘汰的最老值，可以通过一次加减维护总和，并用固定长度数组循环复用存储位置。

解法：环形数组维护滚动和

核心思路

[!blue]

arr 保存最近窗口的元素，长度固定为 size；s 保存当前窗口总和；cnt 记录已经加入的数据总数。下一次写入位置为 idx = cnt % size，位置按数组下标循环前进。

窗口未满时，arr[idx] 是尚未使用的初始零值。窗口已满时，这个槽位上次被写入是在 size 次之前，保存的恰好是旧窗口最早到达的数；加入新值后，它应当被淘汰。

因此先执行 s += val - arr[idx]，扣除旧值并加入新值，再覆盖槽位。未满时扣除的是零，满后扣除的是应淘汰的元素，两种情况都能保持 s 等于新窗口总和。

最后增加 cnt，实际窗口长度就是 min(cnt, size)。用浮点除法计算平均值；size = 1 时每次覆盖唯一槽位，结果就是本次传入值。负数和零也按相同加减规则处理。

解题步骤

1. 构造长度为 size 的全零数组，将总和与计数初始化为 $0$。
2. 每次调用先用增加前的 cnt 计算 idx = cnt % size。
3. 将新值加入总和，并减去槽位中的旧值，之后再覆盖该槽位。
4. 增加 cnt，将总和转为浮点数后除以 min(cnt, size)。

代码实现

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)$，只更新一个槽位和常数个状态。
• 空间复杂度：$O(size)$，固定缓冲区不会随调用次数增长。

关键点总结

[!green]

• 总和通过加入新值、扣除旧值更新，无需重新扫描窗口。
• 循环下标决定覆盖位置，实际数量决定平均值分母。
• 未满窗口中的初始零只参与存储计算，不计入有效数量。

易错点总结

[!yellow]

• 先覆盖槽位再扣除旧值，会丢失真正应移出窗口的数。
• 数据不足窗口大小时仍除以 size，会把未填入的槽位也计入分母。
• 必须先转浮点数再除法，避免整数除法截断小数。
• cnt 同时表示总到达个数，不能在每轮后直接对它取模。

相似题目

题目	难度	关联与区别
933. 最近的请求次数	简单	同样维护最近事件窗口，原题按时间清理，本题按最近固定数量淘汰并维护总和。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/81678186

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！