Swift 实战：用队列巧解 LeetCode 346 数据流中的移动平均数

前言

在数据流处理中，实时计算“滑动窗口内的平均数”是一个非常常见的需求。不论是金融领域的股票价格走势，还是物联网设备的实时数据监控，移动平均（Moving Average） 都是核心操作。

LeetCode 第 346 题“数据流中的移动平均数”就是一道经典的滑动窗口题目，今天我们用 Swift 带大家一步步拆解这道题，写出一个简单又实用的 Demo，顺带聊聊它在实际开发中的应用场景。

描述

题目要求我们设计一个类 MovingAverage，它接受一个整数 size 作为滑动窗口的大小。每次调用 next(val: Int) 方法时，返回最近 size 个数据的平均值。如果数据量不足 size 个，那就用已有的数据来算平均。

题目示例：

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]

输出：
[null, 1.0, 5.5, 4.66667, 6.0]

简单来说：

1. 初始化窗口 size = 3。
2. 数据流依次输入 1、10、3、5。
3. 每次调用 next() 方法都返回窗口内的平均值。

解决方案

我们可以用 队列（Queue）+ 滚动和（rolling sum） 的方式高效解决：

• 队列用来存储滑动窗口中的元素。
• 一个变量 sum 用来记录当前窗口内元素的总和。
• 每次输入新数据后，如果队列长度超过 size，就把最旧的数据踢出去。

Swift 中没有内置的 Queue，我们可以用 Array + removeFirst() 来模拟。

分析问题和答案

直接上代码，后面我们一行行讲解：

class MovingAverage {
    private var windowSize: Int
    private var windowQueue: [Int]
    private var currentSum: Int

    init(_ size: Int) {
        self.windowSize = size
        self.windowQueue = []
        self.currentSum = 0
    }

    func next(_ val: Int) -> Double {
        windowQueue.append(val)
        currentSum += val
        
        if windowQueue.count > windowSize {
            let removed = windowQueue.removeFirst()
            currentSum -= removed
        }
        
        return Double(currentSum) / Double(windowQueue.count)
    }
}

代码拆解：

1. 属性定义：

   • windowSize: 滑动窗口的大小。
   • windowQueue: 模拟队列，记录窗口内的数据。
   • currentSum: 记录当前窗口内元素的总和。

2. 初始化函数 init：

   • 初始化窗口大小，并将队列与总和归零。

3. 核心函数 next(val: Int)：

   • 将新元素加入队列并更新总和。
   • 判断队列是否超出窗口大小，如果是，就把最早的元素从队列中移除，并从总和中减掉。
   • 返回当前窗口内的平均值。

为什么不用每次都去 for 循环 sum？

因为我们用 currentSum 滚动维护了窗口内的总和，每次加入或移除元素时只做一次加减运算，性能是 O(1)，非常高效。

示例测试和结果

来跑一组示例看看效果：

let movingAverage = MovingAverage(3)
print(movingAverage.next(1))  // 输出: 1.0
print(movingAverage.next(10)) // 输出: 5.5
print(movingAverage.next(3))  // 输出: 4.6666666667
print(movingAverage.next(5))  // 输出: 6.0

结果：

1.0
5.5
4.6666666667
6.0

解释：

1. 输入 1 -> 窗口：[1] -> 平均值 1.0
2. 输入 10 -> 窗口：[1, 10] -> 平均值 (1+10)/2 = 5.5
3. 输入 3 -> 窗口：[1, 10, 3] -> 平均值 (1+10+3)/3 = 4.6667
4. 输入 5 -> 窗口：[10, 3, 5] -> 平均值 (10+3+5)/3 = 6.0

时间复杂度

• 每次调用 next 方法的时间复杂度是 O(1)，因为：

  • append 和 removeFirst 是 O(1) 操作。
  • 维护 sum 的加减是 O(1)。

• 整体时间复杂度是 O(n)，n 为调用次数。

控件复杂度

• 队列最多存储 size 个元素。
• 空间复杂度是 O(size)。

总结

这道题看似简单，但“实时数据滑动窗口统计”在很多实际场景都非常重要，比如：

• 股票价格的 N 日均线。
• IoT 设备的实时数据平滑。
• 实时监控系统中的波动过滤。

本题的关键点就在于用一个“队列 + 滚动和”来高效实现 O(1) 的移动平均计算，避免每次都去重复累加。实现逻辑虽然简单，但设计思路却非常有实战意义。