MovingAverageFromDataStreamOPT [source code]

public class MovingAverageFromDataStreamOPT {
    private int currentSize;
    private int maxSize;
    private Node head;
    private Node tail;
    private int totalSum;

    private class Node {
        int val;
        Node next;
        public Node(int v) {
            this.val = v;
            this.next = null;
        }
    }

    /** Initialize your data structure here. */
    public MovingAverageFromDataStreamOPT(int size) {
        currentSize = 0;
        maxSize = size;
        totalSum = 0;
        head = null;
        tail = null;
    }

    public double next(int val) {
        if (maxSize <= 0) {
            return 0;
        }
        if (head == null) {
            head = new Node(val);
            tail = head;
        } else {
            tail.next = new Node(val);
            tail = tail.next;
        }

        currentSize++;
        totalSum += val;
        double average = (double) totalSum / (double) currentSize;

        if (currentSize == maxSize) {
            Node oldHead = head;
            totalSum -= oldHead.val;
            head = head.next;
            currentSize--;
        }
        return average;
    }

    public static void main(String[] args) {
        MovingAverageFromDataStreamOPT m = new MovingAverageFromDataStreamOPT(3);
        int[] input1 = {1,10,3,5};
        for (int i : input1) System.out.println(m.next(i));
    }
}
/**
 * Your MovingAverageFromDataStream object will be instantiated and called as such:
 * MovingAverageFromDataStream obj = new MovingAverageFromDataStream(size);
 * double param_1 = obj.next(val);
 */

这个是最优解, 129ms (不过实际跑起来波动性还是很大的, 我提交的时候就是159ms 了). 好像这个问题的主要纠结的地方就在于用什么结构来保存数据, 这里用的是linked list. 为什么他没有用内置的 list, 不得而知;

大概看了一下, 这个人的代码的逻辑还是比较奇葩的, 大概看看就行了;

Problem Description

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

For example,
MovingAverageFromDataStream m = new MovingAverageFromDataStream(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
Hide Company Tags Google
Hide Tags Design Queue