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); */