LeetCode – Moving Average from Data Stream

Tags: ,

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

Analysis

We can use a bounded queue to record the last n integers in the window, and define a variable sumN to record the sum of the numbers in the window.

Each time when a new number is registered, we update sumN by minus the head of the queue and add the current number. We also remove the head from the queue and append the current number at the end of the queue. 

See the following Java solution:

Extension:

What about calculating the variance of the numbers in the window?