346. Moving Average from Data Stream

346. Moving Average from Data Stream

Easy

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

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

 

Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

 

Constraints:

• 1 <= size <= 1000
• -105 <= val <= 105
• At most 104 calls will be made to next.

문제 접근법

이 문제는 sliding size가 주어질 때, sliding window에 있는 정수들의 합의 평균을 구하는 문제입니다. 

간단하게 매번 for문을 순회하면서 값을 구할수도 있지만, 그렇게 하면 너무 많은 시간이 소요됩니다. 

그렇기 때문에 슬라이딩 윈도우 기법을 사용해서 문제를 풀었습니다. 

/**
 * @param {number} size
 */
var MovingAverage = function(size) {
    this.window = size 
    this.left = 0 
    this.arr = [] 
    this.sum = 0 
};

/** 
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function(val) {
    this.arr.push(val)
    this.sum += val
    
    // size를 넘어선경우 이전값 빼기
    if(this.arr.length > this.window){
        this.sum -= this.arr[this.left++]
    }
    
    const mod = this.arr.length > this.window ? this.window : this.arr.length
    return this.sum / mod
};

/** 
 * Your MovingAverage object will be instantiated and called as such:
 * var obj = new MovingAverage(size)
 * var param_1 = obj.next(val)
 */