346. Moving Average from Data St

Description

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

Queue, O(1), S(k)

这道题的目的就是维护一个滑动窗口，并记录窗口sum，然后滑动到下一个位置时只需要将头尾的差值统计到sum中即可，这样做就能达到O(1)。

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

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

Sliding window, O(1), S(k)

也可以用头尾循环的数组去做，比用queue实现略麻烦一些。

class MovingAverage {

    private int[] window;
    private int nextIndex;
    private int currSize;
    private double sum;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
    }
    
    public double next(int val) {
        if (currSize == window.length) {  // is full
            sum -= window[nextIndex];
            --currSize;
        }
        window[nextIndex] = val;
        ++currSize;
        sum += val;
        nextIndex = ++nextIndex % window.length;
        return sum / currSize;
    }
}

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