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

相关题目

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

发表回复

您的电子邮箱地址不会被公开。