LeetCode - 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
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:
|
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 27 |
import java.util.LinkedList; import java.util.Queue; public class MovingAverage { Queue<Integer> queue; int size; int sumN; /** Initialize your data structure here. */ public MovingAverage(int size) { this.queue = new LinkedList<>(); this.size = size; } public double next(int val) { if (queue.size() <= this.size) { sumN += val; queue.add(val); return sumN * 1.0 / queue.size(); } else { sumN -= queue.poll(); sumN += val; queue.add(val); return sumN * 1.0 / this.size; } } } |
Extension:
What about calculating the variance of the numbers in the window?
