剑指 Offer II 041. 滑动窗口的平均值

题目描述

题目解析

题目在说什么

这道题其实是在模拟一个“滑动窗口”的统计过程。想象你有一个固定大小的“观察框”，比如大小为3。你不断收到新的数字，每次收到一个新数字，你就把这个数字放进框里，同时框里最旧的那个数字就会被挤出去（如果框已经满了）。然后你要计算当前框里所有数字的平均值。

举个例子：

• 窗口大小 = 3
• 第一次收到数字1：框里是[1]，平均值 = 1
• 第二次收到数字2：框里是[1,2]，平均值 = 1.5
• 第三次收到数字3：框里是[1,2,3]，平均值 = 2
• 第四次收到数字4：框满了，把最旧的1挤出去，框里变成[2,3,4]，平均值 = 3

题目要求你实现一个类，每次调用 next(val) 就做一次这样的操作，并返回当前平均值。

---

思路是怎么来的

生活比喻：想象你有一个固定大小的“水杯”，你不断往里面倒水，但水杯满了之后，每倒一次新水，最底下的旧水就会溢出来。你想知道每次倒水后，杯子里水的“平均温度”。

• 你不需要记住杯子里每一滴水的温度，只需要知道总温度和水的滴数。
• 每次新水滴进来，总温度增加新水滴的温度；如果水杯满了，还要减去溢出的那滴水的温度。
• 最后用总温度除以当前水滴数，就是平均温度。

对应到代码：

• 用队列（queue）来模拟“水杯”，队列先进先出，正好对应“最旧的先出去”。
• 用一个变量 sum 记录当前窗口内所有数字的总和，这样每次计算平均值时就不用重新加一遍所有数字，效率高。
• 每次 next(val) 时：

1. 如果队列已满（元素个数等于窗口大小），就先弹出队首（最旧的数字），并从 sum 中减去它。 2. 然后把新数字 val 加入队列，并加到 sum 中。 3. 最后用 sum 除以当前队列长度（即当前窗口内元素个数），得到平均值。

---

代码逐步拆解

我们对照参考代码，一步步看它做了什么：

class MovingAverage {
public:
    MovingAverage(int size) {
        this->size = size;  // 1. 记录窗口大小，比如 size=3
        this->sum = 0;      // 2. 当前窗口内所有数字的和，初始为0
    }

    double next(int val) {
        // 4. 检查队列是否已经满了（队列长度等于窗口大小）
        if (q.size() == size) {
            // 5. 如果满了，先把最左边的数字移出队列，同时从 sum 中减去它
            sum -= q.front();  // q.front() 是队列最前面的元素（最旧的）
            q.pop();           // 弹出队首
        }
        // 6. 把新数字 val 加到 sum 中
        sum += val;
        // 7. 把新数字 val 加入队列末尾
        q.push(val);
        // 8. 计算平均值：sum 除以当前队列长度
        // 注意：需要将 sum 转为 double，否则整数除法会得到整数结果
        return (double)sum / q.size();
    }

private:
    int size;           // 窗口大小
    int sum;            // 当前窗口内所有数字的和
    std::queue<int> q;  // 队列，用来存储窗口中的数字
};

关键点解释：