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

【LetMeFly】低空间消耗解决：剑指 Offer II 041.滑动窗口的平均值

力扣题目链接：https://leetcode.cn/problems/qIsx9U/

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

实现 MovingAverage 类：

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

 

示例：

输入：
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 <= size <= 1000
• -105 <= val <= 105
• 最多调用 next 方法 104 次

 

注意：本题与主站 346 题相同： https://leetcode-cn.com/problems/moving-average-from-data-stream/

方法一：模拟

这道题模拟即可。

• 用int size记录“滑动窗口”的最大大小
• 用int sum记录“滑动窗口”中的所有的值的和
• 用int num记录“滑动窗口”的数字的个数

那么用什么来模拟窗口呢？其实用队列是个非常棒的选择。

但是看这篇标题也可以看出，本题解主要使用低空间消耗来解决问题，因此决定使用静态数组来模拟队列。

因为队列的长度是固定不变的，因此我们开辟数组的时候，开辟的大小就为“滑动窗口”的大小即可。

• 用int* a模拟队列
• 用int loc记录即将要出队的元素的下标

private:
    int size;
    int sum;
    int num;
    int *a;  // Array
    int loc;  // 该移除哪个了

public:
    /** Initialize your data structure here. */
    MovingAverage(int size): size(size), sum(0), num(0), a(new int[size]), loc(0) {

    }

当向“滑动窗口”中添加新的元素时，首先看队列是否已满。

• 若不满则添加新元素
• 若已满则删除旧元素的同时添加新元素

if (num < size) {  // 刚开始，还没填满窗口
    sum += val;
    a[num++] = val;
    return ONE * sum / num;  // 其中ONE是double类型的1
}
else {
    sum -= a[loc];
    sum += val;
    a[loc++] = val;
    loc %= size;
    return ONE * sum / num;
}

运行结果：

如果想要更加严谨一点，可以在类析构的时候deletenew出来的数组

~MovingAverage() {
    delete[] a;
}

运行时间竟然减少了

• 时间复杂度$O(n)$，其中$n$是要添加的元素的个数
• 空间复杂度$O(m)$，其中$m$是“滑动窗口”的大小

AC代码

C++

const double ONE = 1;

class MovingAverage {
private:
    int size;
    int sum;
    int num;
    int *a;  // Array
    int loc;  // 该移除哪个了
public:
    /** Initialize your data structure here. */
    MovingAverage(int size): size(size), sum(0), num(0), a(new int[size]), loc(0) {

    }

    ~MovingAverage() {
        delete[] a;
    }
    
    double next(int val) {
        if (num < size) {  // 刚开始，还没填满窗口
            sum += val;
            a[num++] = val;
            return ONE * sum / num;
        }
        else {
            sum -= a[loc];
            sum += val;
            a[loc++] = val;
            loc %= size;
            return ONE * sum / num;
        }
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125819216