LeetCode 346. Moving Average from Data Stream 原创Java参考解答
问题描述
https://leetcode.com/problems/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
解题思路
题目是设计一个叫MovingAverage的数据结构，使其能在不断更新的过程中始终求出平均值。
从题目例子可以看到，初始化size为3的MovingAverage在通过next()加入了3个元素1、10、3后，容量充满。这时当MovingAverage添加第4个元素5时候，需要先去掉最早加入的元素1。如果能够联想到这个数据结构的实质就是个先进先出的队列，那么这道题就可以迎刃而解。
这个题可能出现follow up问题：面试官可能会问你，如果数据很大的情况，比如超过 1TB 的数据的 average，那该怎么办？Queue都存在内存里，1TB的数据内存存不下如何是好？
答案是放在硬盘上，比如放在数据库里。我们记录在硬盘上的值，可以用前缀和（ PrefixSum ）的形式。当你需要计算某一段的和的时候，只需要用当前的前缀和减去之前某个时刻的前缀和就可以了。这样对于硬盘来说，只是1次读写操作。
参考代码
public class MovingAverage {
private int windowMaxSize;
private double previousSum;
private Queue<Integer> window;
/** Initialize your data structure here. */
public MovingAverage(int size) {
this.windowMaxSize = size;
this.window = new LinkedList<>();
}
public double next(int val) {
if (window.size() == windowMaxSize) {
previousSum -= window.poll();
}
window.offer(val);
previousSum += val;
return previousSum / window.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/