数据流中的移动平均值

一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第7天，点击查看活动详情。

笔者除了大学时期选修过《算法设计与分析》和《数据结构》还是浑浑噩噩度过的（当时觉得和编程没多大关系），其他时间对算法接触也比较少，但是随着开发时间变长对一些底层代码/处理机制有所接触越发觉得算法的重要性，所以决定开始系统的学习（主要是刷力扣上的题目）和整理，也希望还没开始学习的人尽早开始。

系列文章收录《算法》专栏中。

力扣题目链接

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。 double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。 [ "MovingAverage" , "next" , "next" , "next" , "next" ] [[3] , [1] , [10] , [3] , [5] ] [null, 1.0, 5.5, 4.66667, 6.0] MovingAverage movingAverage = new MovingAverage ( 3 ); movingAverage .next ( 1 ); // 返回 1.0 = 1 / 1 movingAverage .next ( 10 ); // 返回 5.5 = (1 + 10) / 2 movingAverage .next ( 3 ); // 返回 4.66667 = (1 + 10 + 3) / 3 movingAverage .next ( 5 ); // 返回 6.0 = (10 + 3 + 5) / 3


      1 <= size <= 1000


      -105 <= val <= 105

最多调用


      next

方法


      10^4

次

我们可以先分析下题目：

数据流就是说数据是流动的，即不断增加。

窗口大小有点像滑块，即包含一个子集数据，计算窗口内子集的平均值。

那么我们就可以使用队列，队列具备先进先出的特点，符合数据流动，流过去的数据就直接出队列。我们需要计算平均值，可以在过程中进行累加，出队列的值就需要减掉，next方法返回即使用累加值除以出队后的队列大小即可。

package com.study.algorithm.queue;
import java.util.ArrayDeque;
import java.util.Deque;
public class MovingAverage {
    private int size;
    private int windowSum = 0;
    private Deque<Integer> deque = new ArrayDeque();
    public MovingAverage(int size) {
        this.size = size;
    public double next(int val) {
        deque.offer(val);
        //队列大小
        int count = deque.size();
        //队列最多放size+1个元素，如果大于size就要把头部弹出表示数据已经流过
        int head = count > size ? deque.poll() : 0;
        //需要减去已经流过的数据值
        windowSum = windowSum - head + val;
        //求平均值
        return windowSum * 1.0 / Math.min(size, count);
    public static void main(String[] args) {
        MovingAverage movingAverage = new MovingAverage(3);
        System.out.println(movingAverage.next(1));// 返回 1.0 = 1 / 1
        System.out.println(movingAverage.next(10)); // 返回 5.5 = (1 + 10) / 2
        System.out.println(movingAverage.next(3)); // 返回 4.66667 = (1 + 10 + 3) / 3
        System.out.println(movingAverage.next(5)); // 返回 6.0 = (10 + 3 + 5) / 3
其实笔者是因为面试的时候问到了：“存在一个业务，不断有价格数据产生，毫秒级别的产生，需要实时返回5分钟内的所有价格平均价格”。
面试官还是比较好的，提示了我用移动平均值算法，后面我也没有多问了。
针对于这个题，确实可以使用移动平均数，由于笔者也不知道具体业务场景，我们可以每10ms拉取一次价格数据，那么我们同样也可以使用一个大小为5*60*100+1的队列去存放这些数据。但是因为数据不一定是10ms产生一次，那么如果没有拉取到，我们就直接存放上一个价格，也是符合业务的。