【C/C++】剑指 Offer II 041. 滑动窗口的平均值

---

题目链接：剑指 Offer II 041. 滑动窗口的平均值

题目描述

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

提示:

• 1⩽size⩽10001 \leqslant size \leqslant 10001⩽size⩽1000
• −105 ⩽val⩽105-10^5 \leqslant val \leqslant 10^5−105 ⩽val⩽105
• 最多调用 next 方法 10410^4104 次

示例 1：

输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

整理题意

题目给定一个滑动窗口的大小，并给出一个数据流，每次给定一个整数，将整数放入滑动窗口计数滑动窗口中整数的平均值。当滑动窗口装满时，满足先进先出规则。

解题思路分析

由于题目规定滑动窗口中的数据满足先进先出规则，我们可以使用 队列 来模拟实现这一过程，用一个变量记录队列中所有元素的总和，当队列中的元素超过滑动窗口大小时将队头元素弹出，并维护此时队列元素中所有元素的和。每次返回队列中所有元素的平均值即可。

具体实现

1. 记录滑动窗口大小，初始化队列。
2. 将给定数据压入队列，并判断队列中元素个数是否超过滑动窗口大小。
3. 当超过滑动窗口大小时从队头进行弹出元素，并且不断维护队列中元素的总和。
4. 返回队列元素总和除以队列中的元素个数即得滑动窗口中元素的平均值。

复杂度分析

• 时间复杂度：初始化和每次调用 next 的时间复杂度都是 O(1)O(1)O(1)。
• 空间复杂度：O(size)O(size)O(size)，其中 size 是滑动窗口的大小。空间复杂度主要取决于队列，队列中的数字个数不超过 size。

代码实现

class MovingAverage {
private:
    queue<int> que;
    int n;
    double sum;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        //记录滑动窗口大小
        n = size;
        //sum记录队列中元素总和
        sum = 0;
        //清空队列
        while(que.size()) que.pop();
    }
    
    double next(int val) {
        //维护队列中元素总和
        sum += val;
        que.push(val);
        //维护队列中的元素个数不超过滑动窗口大小
        while(que.size() > n){
            sum -= que.front();
            que.pop();
        }
        //返回平均值
        return sum / (double)que.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

总结

• 该题的核心在于理解题意，其次在于对 队列 数据结构的运用。
• 计算队列中所有元素和可以使用一个变量进行记录，通过维护队列总所有元素总和，可以 O(1) 进行计算队列中所有元素的平均值。
• 测试结果：

结束语

学习对一个人的重要性，不只在于习得新知识，更在于帮助我们保持思考的习惯，继而不断成长。让学习成为一种习惯，你所收获的，将会是应对生活的底气和智慧。新的一天，加油！