LeetCode 346. Moving Average from Data Stream 原创Java参考解答

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的数据结构,使其能在不断更新的过程中始终求出平均值。

从题目例子可以看到,初始化size为3的MovingAverage在通过next()加入了3个元素1、10、3后,容量充满。这时当MovingAverage添加第4个元素5时候,需要先去掉最早加入的元素1。如果能够联想到这个数据结构的实质就是个先进先出的队列,那么这道题就可以迎刃而解。

这个题可能出现follow up问题:面试官可能会问你,如果数据很大的情况,比如超过 1TB 的数据的 average,那该怎么办?Queue都存在内存里,1TB的数据内存存不下如何是好?

答案是放在硬盘上,比如放在数据库里。我们记录在硬盘上的值,可以用前缀和( PrefixSum )的形式。当你需要计算某一段的和的时候,只需要用当前的前缀和减去之前某个时刻的前缀和就可以了。这样对于硬盘来说,只是1次读写操作。

参考代码

相关题目

LeetCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注