moving-average-from-data-stream

Moving Average from Data Stream – LeetCode 346

Problem

Description

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Answer

Original

Code

class MovingAverage {
public:
    MovingAverage(unsigned size):size(size), sum(0){ }
    
    double next(int val) {
        if (q.size() == size) {
            sum -= q.front(); q.pop();
        }
        q.push(val);
        sum += val;
        return sum / q.size();
    }
    
private:
    queue<int> q;
    int size;
    double sum;
};

思路

适合使用FIFO的queue来实现，然后在next中实现滑动窗口的效果就行了。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。