346. Moving Average from Data Stream

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

For 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

Solution:

The idea is to create a queue as a sliding window.

If the size of the queue equals to the window size, we poll the first item and decrease the sum.

Then we offer the value to the queue and add it to sum.

Finally we return sum / queue size.



Code:

public class MovingAverage {
    
    private double sum;
    private int size;
    private Queue<Integer> window;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
        this.sum = 0;
        this.window = new LinkedList<>();
    }
    
    public double next(int val) {
        if (window.size() == size) {
            sum -= window.poll();
        }
        sum += val;
        window.offer(val);
        return sum / window.size();
    }
}

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