Leetcode 分類刷題 —— 隊(duì)列（Queue）

1、題目

Leetcode 346. Moving Average from Data Stream

• 實(shí)現(xiàn) MovingAverage 類：

MovingAverage(int size) 用窗口大小 size 初始化對(duì)象。
double next(int val) 成員函數(shù) next 每次調(diào)用的時(shí)候都會(huì)往滑動(dòng)窗口增加一個(gè)整數(shù)，請(qǐng)計(jì)算并返回?cái)?shù)據(jù)流中最后 size 個(gè)值的移動(dòng)平均值，即滑動(dòng)窗口里所有數(shù)字的平均值。

2、思路

使用一個(gè)固定大小的隊(duì)列來(lái)表示窗口，每次插入數(shù)據(jù)前判斷隊(duì)列是否已滿，滿了就刪除隊(duì)列的頭元素，再在隊(duì)列的尾部插入元素。
為避免頻繁求和，使用一個(gè)sum變量保存隊(duì)列里面元素的和。

3、Java 代碼

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