[LeetCode] 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

Thought process:
Use queue.

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

class MovingAverage { private double sum; private int capacity; private Queue<Integer> queue; /** Initialize your data structure here. */ public MovingAverage(int size) { capacity = size; sum = 0; queue = new LinkedList<>(); } public double next(int val) { if (queue.size() == capacity) { sum -= queue.poll(); } queue.offer(val); sum += val; return sum / queue.size(); } } /** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */

Time complexity:

• Constructor: O(1).
• next(): O(1).