『LeetCode』剑指 Offer II 041 滑动窗口的平均值

题目

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

实现 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
\(-10^{5} <= val <= 10^{5}\)
最多调用 next 方法 \(10^{4}\) 次

注意：本题与主站 346 题相同： https://leetcode-cn.com/problems/moving-average-from-data-stream/ (这个是会员题...)

题解

【滑动窗口的平均值】简单模拟

模拟

使用队列模拟即可，没有队列数据结构的也可以使用循环数组手动实现

# Code language: Python
class MovingAverage:

    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.st = deque(maxlen=size)
        self.cnt = 0

    def next(self, val: int) -> float:
        if len(self.st) == self.st.maxlen:
            self.cnt -= self.st.popleft()
        self.st.append(val)
        self.cnt += val
        return self.cnt / len(self.st)

// Code language: Java
class MovingAverage {
    Deque<Integer> st = new ArrayDeque<>();
    int n, cnt;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        n = size; cnt = 0;
    }
    
    public double next(int val) {
        if (st.size() == n) cnt -= st.pollFirst();
        cnt += val;
        st.addLast(val);
        return (double) cnt / st.size();
    }
}

// Code language: C++
class MovingAverage {
public:
    /** Initialize your data structure here. */
    queue<int> st;
    int n, cnt;
    MovingAverage(int size): n(size), cnt(0) {
    }
    
    double next(int val) {
        if (st.size() == n) cnt -= st.front(), st.pop();
        cnt += val;
        st.push(val);
        return (double) cnt / st.size();
    }
};

// Code language: C
typedef struct {
    int n, sum, cnt, top, tail;
    int* st;
} MovingAverage;

/** Initialize your data structure here. */

MovingAverage* movingAverageCreate(int size) {
    MovingAverage* obj = (MovingAverage*) malloc(sizeof(MovingAverage));
    obj->n = size; obj->sum = 0; obj-> cnt = 0; obj->top = 0; obj->tail = 0;
    obj->st = (int*) malloc(sizeof(int) * size);
    return obj;
}

double movingAverageNext(MovingAverage* obj, int val) {
    if (obj->cnt > 0 && (obj->top + obj->n - obj->tail) % obj->n == 0) {
        obj->sum -= obj->st[obj->tail];
        obj->tail = (obj->tail + 1) % obj->n;
        obj->cnt--;
    }
    obj->sum += val;
    obj->st[obj->top] = val;
    obj->top = (obj->top + 1) % obj->n;
    obj->cnt++;
    return (double) obj->sum / obj->cnt;
}

void movingAverageFree(MovingAverage* obj) {
    free(obj->st);
    free(obj);
}

/** JavaScript
 * Initialize your data structure here.
 * @param {number} size
 */
var MovingAverage = function(size) {
    this.st = new Array(size).fill(0);
    this.n = size;
    this.sum = 0;
    this.cnt = 0;
    this.top = 0;
    this.tail = 0;
};

/** 
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function(val) {
    if (this.cnt > 0 && (this.top + this.n - this.tail) % this.n == 0) {
        this.sum -= this.st[this.tail];
        this.tail = (this.tail + 1) % this.n;
        this.cnt -= 1;
    }
    this.sum += val;
    this.st[this.top] = val;
    this.top = (this.top + 1) % this.n;
    this.cnt += 1;
    return this.sum / this.cnt;
};

时间复杂度: 初始化及 next 操作均为 \(O(1)\)
空间复杂度: \(O(size)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』剑指 Offer II 041 滑动窗口的平均值

题目

标签

题解

模拟