0346._Moving_Average_from_Data_Stream.md

346. Moving Average from Data Stream

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/moving-average-from-data-stream/

内容描述

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

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

beats 100%

class MovingAverage:

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.avg = 0.0
        self.count = 0
        self.window = collections.deque()
        

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.window.append(val)
        
        if self.count < self.size:
            self.count += 1
            self.avg += (val - self.avg) / self.count
        else:
            tmp = self.window.popleft()
            self.avg += (val - tmp) / self.size
            
        return self.avg