给出一串整数流和窗口大小，计算滑动窗口中所有整数的平均值。

在线做题地址

样例 1 :

MovingAverage m = new MovingAverage(3); m.next(1) = 1 // 返回 1.00000 m.next(10) = (1 + 10) / 2 // 返回 5.50000 m.next(3) = (1 + 10 + 3) / 3 // 返回 4.66667 m.next(5) = (10 + 3 + 5) / 3 // 返回 6.00000 

解题思路

我们需要一个数据结构来维护在窗口中的值，这个数据结构有一个要求，当存储的数个数大于窗口大小 m 时，需要弹出最先进入的数，这正好时队列的性质，所以可以用队列来维护。

算法：队列模拟滑动窗口

1. 初始化时新建一个队列。
2. 每次调用 next(x)时，将 x 加入队列 1 。
3. 如果队列长度大于 m，弹出队首。
4. 计算结果并返回。

复杂度分析

设窗口大小为 m 。 时间复杂度

• 单次 next()时间复杂度 O(1)
• 队列插入和弹出都是 O(1)。 空间复杂度
• 最多存储 m 个数，空间复杂度为 O(m)。

public class MovingAverage {      private Queue<Integer> queue;     private double sum = 0;     private int size;      /** Initialize your data structure here. */     public MovingAverage(int size) {         queue = new LinkedList<Integer>();         this.size = size;     }          public double next(int val) {         sum += val;         if (queue.size() == size) {             sum = sum - queue.poll();         }         queue.offer(val);         return sum / queue.size();     } }  

大佬有話說 (0)