November 28, 2019

346. Moving Average from Data Stream

Naive Solution using Array: Time = O(n), Space = O(n)

Optimized Solution:

Reduce time: Keep track of previous sum 用前缀和数组
Reduce space: Keep a sliding window using Queue
Time = O(1), Space = O(n)

class MovingAverage {
    
    private Queue<Integer> queue;
    private int size;
    private int windowSum;

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

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