劍指 Offer II 041. 滑動視窗的平均值 : 簡單模拟題

題目描述

這是 LeetCode 上的 ​​劍指 Offer II 041. 滑動視窗的平均值​​ ，難度為 簡單。

Tag : 「模拟」、「隊列」

給定一個整數資料流和一個視窗大小，根據該滑動視窗的大小，計算滑動視窗裡所有數字的平均值。

實作 ​

​MovingAverage​

​ 類：

• ​

  ​MovingAverage(int size)​

  ​​ 用視窗大小​

  ​size​

  ​ 初始化對象。
• ​

  ​double next(int val)​

  ​​ 成員函數​

  ​next​

  ​​ 每次調用的時候都會往滑動視窗增加一個整數，請計算并傳回資料流中最後​

  ​size​

  ​ 個值的移動平均值，即滑動視窗裡所有數字的平均值。

示例：

輸入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[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      

提示：

• 最多調用​

  ​next​

  ​​ 方法

雙端隊列

根據題意，我們可以使用變量 ​

​n​

​​ 将初始化傳入的 ​

​size​

​​ 進行轉存，同時使用「雙端隊列」來存儲 ​

​next​

​​ 所追加的值（添加到隊列尾部），當雙端隊列所包含元素超過規定數量 ​

​n​

​​ 時，我們從隊列頭部進行 ​

​pop​

​​ 操作，整個維護過程使用變量 ​

​sum​

​ 記錄目前包含的元素和。

利用 ​

​next​

​​ 操作最多被調用 次，我們可以使用直接開個 數組來充當雙端隊列，使用兩指針 ​​

​j​

​​ 和 ​

​i​

​ 分别指向隊列的頭部和尾部。

Java 代碼：

class MovingAverage {
    int[] arr = new int[10010];
    int n, sum, j, i;
    public MovingAverage(int {
        n = size;
    }
    public double next(int {
        sum += arr[i++] = val;
        if (i - j > n) sum -= arr[j++];
        return sum * 1.0      

Typescript 代碼：

class MovingAverage {
    arr: number[] = new Array<number>(10010).fill(0)
    n: number = 0; sum: number = 0; i: number = 0; j: number = 0;
    constructor(size: number) {
        this.n = size
    }
    next(val: number): number {
        this.sum += this.arr[this.i++] = val
        if (this.i - this.j > this.n) this.sum -= this.arr[this.j++]
        return this.sum / (this.i - this.j)
    }
}      

• 時間複雜度：，其中為​​

  ​next​

  ​ 操作的調用次數
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​劍指 Offer II 041​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。