Moving Average from Data Stream

Queue, Design

Easy

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

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

用Queue来实现先进先出这样的模式，同时根据应用场景，只需要计算均值，因此额外存一个元素总和sum即可，随着poll(), offer()来更新sum。

可用LinkedList，或者固定长度的array。

算法复杂度 O(1) time, O(k) space

Solution

Queue (Implemented with LinkedList)

(137ms 59.29%)

class MovingAverage {
    private int sum;
    private Queue<Integer> queue;
    private int capacity;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        queue = new LinkedList<Integer>();
        sum = 0;
        capacity = size;
    }

    public double next(int val) {
        if (queue.size() == capacity) {
            int sub = queue.poll();
            sum = sum - sub;
        }
        queue.offer(val);
        sum = sum + val;

        return (double) sum / queue.size();
    }
}

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

Another simpler implementation using LinkedList as Queue

class MovingAverage {

    Queue<Integer> q;
    double sum = 0;
    int size;

    public MovingAverage(int s) {
        q = new LinkedList();
        size = s;
    }

    public double next(int val) {
        if(q.size() == size){
            sum = sum - q.poll();
        }
        q.offer(val);
        sum += val;
        return sum/q.size();
    }
}

Using ArrayDeque

class MovingAverage {
    Deque<Integer> q;
    int sum;
    int size;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
        sum = 0;
        q = new ArrayDeque<Integer>();
    }

    public double next(int val) {
        if (size == q.size()) {
            sum -= q.poll();
        }
        sum += val;
        q.offer(val);
        return 1.0 * sum / q.size();
    }
}

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

Using fixed length Array (Circular Queue)

(74 ms, faster than 100.00%, 43 MB, less than 59.43%)

用固定长度Array，insertIdx作为下一个数字的位置，每次next()时，要先更新当前sum，再加上新的val。同时要注意的是追踪目前填入了多少个数字，如果小于window长度，则需要用当前填入数字的计数作为分母计算average。

public class MovingAverage {
    private int [] window;
    private int n, insert;
    private long sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        insert = 0;
        sum = 0;
    }

    public double next(int val) {
        if (n < window.length)  n++;
        sum -= window[insert];
        sum += val;
        window[insert] = val;
        insert = (insert + 1) % window.length;

        return (double)sum / n;
    }
}

Another implementation

class MovingAverage {
    int[] window;
    int count;
    int capacity;
    int insertIdx;
    int sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        count = 0;
        capacity = size;
        insertIdx = 0;
        sum = 0;
    }

    public double next(int val) {
        if (count < capacity) {
            count++;
        } else {
            sum -= window[insertIdx];
        }
        window[insertIdx] = val;
        sum += val;
        insertIdx = (insertIdx + 1) % capacity;
        int size = Math.min(count, capacity);
        return 1.0 * sum / size;
    }
}

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