关注文末推广名片，即可免费获得本题测试源码！

题目来源：🔒LeetCode 346. 数据流中的移动平均值

问题抽象： 设计一个 MovingAverage 类，用于实时计算数据流中 固定窗口大小 的移动平均值，满足以下核心需求：

1. 核心功能：

   • 初始化时指定窗口大小 size；
   • 每次调用 next(val) 时：
     • 将新值 val 加入窗口末尾；
     • 若窗口元素数超过 size，则移除最早加入的值；
     • 返回当前窗口内所有元素的 算术平均值（浮点数）。

2. 计算约束：

   • 时间复杂度 O(1)：单次 next 操作需常数时间（避免遍历求和）；
   • 空间复杂度 O(size)：存储窗口元素（队列或循环数组）；
   • 利用 累加和优化：维护窗口元素和，更新时减去移出值、加上新值。

3. 边界处理：

   • 初始空窗口：next(1) 返回 1.0（仅一个元素）；
   • 窗口未满：平均值按实际元素数计算（如 size=3 时，前两次调用取 2 个元素的平均值）；
   • 窗口已满：移除最早元素（如 size=3 时，第四次调用移除第一个元素）；
   • 特殊输入：size=0 时返回 0（但题目保证 size>0）。

类定义：

class MovingAverage:
    def __init__(self, size: int):  # 初始化窗口大小  
    def next(self, val: int) -> float:  # 添加新值并返回当前平均值  

解题思路

题目要求实现一个 MovingAverage 类，用于计算数据流中最近 size 个元素的移动平均值。核心思路如下：

1. 数据结构选择：使用队列（Queue）存储数据流元素，队列天然支持先进先出（FIFO），适合维护滑动窗口。
2. 维护窗口和总和：
   • 初始化时记录窗口大小 size，初始化队列和总和变量 sum。
   • 每次添加新元素时：
     • 若队列已满（达到 size），移除队首元素并从 sum 中减去该值。
     • 将新元素加入队列，并累加到 sum。
3. 计算平均值：用当前总和 sum 除以队列中实际元素数量（可能小于 size），直接返回结果。
4. 时间复杂度：next() 操作时间复杂度为 $O(1)$，空间复杂度为 $O(size)$。

代码实现（Java版）🔥点击下载源码

class MovingAverage {
    private final int size;   // 滑动窗口大小
    private double sum;       // 窗口内元素总和
    private Queue<Integer> queue; // 存储元素的队列

    public MovingAverage(int size) {
        this.size = size;
        this.sum = 0.0;
        this.queue = new LinkedList<>();
    }
    
    public double next(int val) {
        // 当队列大小达到窗口大小时，移除队首元素并更新总和
        if (queue.size() == size) {
            sum -= queue.poll();
        }
        // 新元素入队并更新总和
        queue.offer(val);
        sum += val;
        // 计算平均值：总和 / 当前队列元素个数
        return sum / queue.size();
    }
}

代码说明

1. 初始化：
   • size 存储滑动窗口大小。
   • sum 初始化为 0.0，用于动态维护窗口内元素总和。
   • queue 使用 LinkedList 实现队列，支持高效入队（offer）和出队（poll）操作。
2. next() 方法：
   • 队列满处理：当队列元素数量等于 size 时，移除队首元素并从 sum 中减去该值。
   • 新元素入队：将新元素加入队尾，并累加到 sum。
   • 计算平均值：用当前 sum 除以队列实际大小（可能小于 size），直接返回平均值。
3. 优势：
   • 高效：每次操作仅涉及一次出队和一次入队，时间复杂度 $O(1)$。
   • 低内存：队列最多存储 size 个元素，空间复杂度 $O(size)$。
   • 精确：使用 double 维护总和，避免整数除法精度损失。