难度: Easy
Submission
运行时间: 41 ms
内存: 19.2 MB
class MovingAverage:
def __init__(self, size: int):
self.size = size
self.queue = deque()
self.sum_v = 0
def next(self, val: int) -> float:
self.sum_v += val
self.queue.append(val)
if len(self.queue)>self.size:
self.sum_v -= self.queue.popleft()
return self.sum_v/len(self.queue)
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
Explain
该题解使用了双端队列 deque 来实现移动平均值的计算。在初始化时，记录了窗口大小 size，并初始化了一个双端队列 queue 和滑动窗口内的元素和 sum_v。在每次调用 next 方法时，将新的元素 val 加入队列，并更新窗口内元素和 sum_v。如果队列长度超过了窗口大小 size，就将队首元素弹出，并相应地减少 sum_v。最后返回 sum_v 除以队列长度，即为当前的移动平均值。
时间复杂度: O(1)
空间复杂度: O(size)
class MovingAverage:
def __init__(self, size: int):
self.size = size # 记录窗口大小
self.queue = deque() # 初始化双端队列
self.sum_v = 0 # 初始化窗口内元素和
def next(self, val: int) -> float:
self.sum_v += val # 更新窗口内元素和
self.queue.append(val) # 将新元素加入队列
if len(self.queue) > self.size: # 如果队列长度超过窗口大小
self.sum_v -= self.queue.popleft() # 弹出队首元素，并更新元素和
return self.sum_v / len(self.queue) # 返回移动平均值
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
Explore
在`MovingAverage`类的初始化中，`size`用于设置滑动窗口的大小，这是计算移动平均值的核心参数。`queue`作为双端队列，用于存储滑动窗口中的元素，这使得元素的进入和退出都可以高效地进行。`sum_v`则用于存储当前队列中所有元素的和，这样在每次计算移动平均值时，可以避免重新遍历队列计算总和，提高效率。整体来看，这三个属性共同维护了滑动窗口的状态，是算法实现的基础。
双端队列`deque`被选择是因为它支持两端的高效元素添加和删除操作（均为O(1)时间复杂度）。对比之下，列表（如Python中的list）在列表的起始位置插入或删除元素的时间复杂度是O(n)，因为需要移动其他所有元素。虽然链表可以支持O(1)时间复杂度的元素添加和删除，但在Python中使用链表（如实现自定义链表或使用库）通常不如直接使用`deque`方便和高效。因此，`deque`是实现滑动窗口这种数据结构的理想选择。
在`next`方法中，当队列长度超过窗口大小时，简单地减去队首元素的处理方式是准确的，前提是没有发生数据类型溢出或精度问题。在常规使用中，只要确保`sum_v`的数据类型（如Python中的int）能够处理累加值的大小，这种实现就不会导致计算不准确。Python的int类型通常可以处理非常大的整数，因此在一般情况下不会有问题。
当窗口未满时，直接使用`sum_v`除以当前队列长度是合适的，因为这反映了窗口内实际存在的所有元素的平均值。这种处理方式确保了在任何时候计算得到的都是当前窗口内所有元素的真实平均值。因此，无论窗口是否已满，这种计算方法都是正确和适当的。