*346. Moving Average from Data Stream

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

solution

• 双端队列

from collections import deque

class MovingAverage: 
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.sum = 0
    
    def next(self, val: int) -> float:
        if len(self.queue) == self.size:
            left_val = self.queue.popleft()
            self.sum -= left_val
        
        self.queue.append(val)
        self.sum += val
        return self.sum / len(self.queue)

时间复杂度：O(1) 空间复杂度：O(n)

• 列表

class MovingAverage: 
    def __init__(self, size: int):
        self.size = size
        self.nums = []
        self.sum = 0
    
    def next(self, val: int) -> float:
        self.nums.append(val)
        self.sum += val
        if len(self.nums) > self.size:
            self.sum -= self.nums.pop(0)
        return self.sum / len(self.nums)

时间复杂度：O(n) 空间复杂度：O(n)