346. Moving Average from Data Stream

346. Moving Average from Data Stream (Easy)

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

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

 

Companies:
Facebook, Google, Bloomberg, Twitter, Uber

Related Topics:
Design, Queue

Solution 1.

// OJ: https://leetcode.com/problems/moving-average-from-data-stream/
// Author: github.com/lzl124631x
// Time:
//     MovingAverage: O(1)
//     next: O(1)
// Space: O(S)
class MovingAverage {
private:
    queue<int> q;
    int size, sum = 0;
public:
    MovingAverage(int size) : size(size) { }
    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double)sum / q.size();
    }
};