大廠面試真題詳解：資料流滑動視窗平均值

給出一串整數流和視窗大小，計算滑動視窗中所有整數的平均值。

線上評測位址：

領扣題庫官網 樣例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();
    }
}           

更多題解參考：

九章官網solution