题目

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

示例:

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

方案一

class MovingAverage:
    '''
    使用列表实现
    '''
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.size = size
        self._list = []

    def next(self, val: int) -> float:
        self._list.append(val)
        if len(self._list) < self.size:
            return sum(self._list) / len(self._list)
        else:
            return sum(self._list[-self.size:]) / self.size

• 使用列表来实现, 缺点是会造成很多空间浪费
• 每次都求和也会造成性能损失

leetcode 执行用时：116 ms

方案二

class MovingAverage:
    '''
    使用内置deque实现
    '''
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self._deque = collections.deque(maxlen=size)

    def next(self, val: int) -> float:
        self._deque.append(val)
        return sum(self._deque) / len(self._deque)

• 使用队列实现

leetcode 执行用时：96 ms

方案三

class MovingAverage:
    '''
    优化方案二求和过程
    '''

    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self._deque = collections.deque(maxlen=size+1)
        self._sum = 0
        self.size = size

    def next(self, val: int) -> float:
        self._deque.append(val)
        self._sum += val
        if self._deque.maxlen == len(self._deque): # 满了
            self._sum -= self._deque[0]
            return self._sum / self.size
        return self._sum / len(self._deque)

• 优化方案二每次的求和过程

  leetcode 执行用时：80 ms

一个更好的写法

class MovingAverage:

    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self._deque = collections.deque(maxlen=size)
        self._sum = 0
        self.size = size

    def next(self, val: int) -> float:
        if len(self._deque) >= self.size:
            self._sum -= self._deque.popleft()
        self._deque.append(val)
        self._sum += val
        return self._sum / len(self._deque)

原题

https://leetcode-cn.com/explore/learn/card/queue-stack/216/queue-first-in-first-out-data-structure/868/