问题描述

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

测试样例

1
2
3
4
5
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

解题

思路

使用队列来保存窗口数据，保持队列小于等于窗口大小，并记录窗口元素值方便计算平均值。

补充：

  1. 队列
  2. 时间复杂度 O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Queue;

public class MovingAverage {

    private Queue<Integer> queue;
    private int window_sz;
    private double window_sum;

    /*
    * @param size: An integer
    */public MovingAverage(int size) {
        // do intialization if necessary
        queue = new LinkedList<Integer>();
        window_sz = size;
        window_sum = 0;
    }

    /*
     * @param val: An integer
     * @return:  
     */
    public double next(int val) {
        // 容量满时，弹出队首元素
        if(queue.size() == window_sz) {
            window_sum -= queue.poll();
        }
        
        // 新元素加入队尾
        queue.offer(val);
        window_sum += val;

        return window_sum / queue.size();
    }
}