Problem description:

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

Example:

1
2
3
4
5
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

Solution:

The idea is to use a queue to store the input and check if the size exceed the limit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size): sum(0) {
        this->size= size;
    }
    
    double next(int val) {
        if(q.size()>= size){
            sum-= q.front(); q.pop();
        }
        q.push(val);
        sum+= val;
        return q.size() == size? (sum/size): (sum/q.size());
    }
    
    queue<int> q;
    int size;
    double sum;
};

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

time complexity: $O(1)$
space complexity: $O(n)$
reference:
https://goo.gl/R1YzHh