LeetCode 第346题：数据流中的移动平均值

📖 文章摘要

本文详细解析LeetCode第346题“数据流中的移动平均值”，这是一道简单难度的数据结构设计题目。文章提供了基于队列和数组两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要学习数据流处理和滑动窗口的程序员。

核心知识点： 队列、滑动窗口、数据流处理
难度等级： 简单
推荐人群： 初学算法的程序员，想要掌握数据流处理的开发者

题目描述

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

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象
double next(int val) 计算并返回数据流中最后 size 个值的移动平均值

示例

示例 1：

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1);  // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3);  // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5);  // 返回 6.0 = (10 + 3 + 5) / 3

提示

1 <= size <= 1000
-105 <= val <= 105
最多调用 next 方法 104 次

解题思路

方法一：队列实现

使用队列维护滑动窗口内的元素。

关键点：

使用队列存储窗口内的元素
维护窗口内元素的总和
当队列长度超过窗口大小时移除最早的元素
计算平均值时考虑实际元素个数

具体步骤：

初始化队列和窗口大小
添加新元素时：
- 将元素加入队列
- 更新总和
- 如果超出窗口大小，移除最早的元素
返回平均值

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

方法二：循环数组

使用固定大小的数组和一个指针实现循环队列。

关键点：

使用数组存储元素
使用指针标记当前位置
通过取模运算实现循环
维护窗口内元素的总和

图解思路

队列实现分析表

操作	队列内容	窗口和	平均值	说明
next(1)	[1]	1	1.0	第一个元素
next(10)	[1,10]	11	5.5	两个元素
next(3)	[1,10,3]	14	4.67	三个元素
next(5)	[10,3,5]	18	6.0	移除最早的1

循环数组示意图

size = 3的循环数组：
[0][1][2]
 ↑
当前位置

添加元素后：
[1][0][0]
   ↑
下一位置

继续添加：
[1][10][0]
      ↑
下一位置

代码实现

C# 实现

public class MovingAverage {
    private Queue<int> queue;
    private int size;
    private double sum;
    
    public MovingAverage(int size) {
        this.queue = new Queue<int>();
        this.size = size;
        this.sum = 0;
    }
    
    public double Next(int val) {
        queue.Enqueue(val);
        sum += val;
        
        if (queue.Count > size) {
            sum -= queue.Dequeue();
        }
        
        return sum / Math.Min(size, queue.Count);
    }
}

Python 实现

from collections import deque

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

C++ 实现

class MovingAverage {
private:
    queue<int> q;
    int size;
    double sum;
    
public:
    MovingAverage(int size) {
        this->size = size;
        this->sum = 0;
    }
    
    double next(int val) {
        q.push(val);
        sum += val;
        
        if (q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        
        return sum / min(size, (int)q.size());
    }
};

执行结果

C# 实现

执行用时：120 ms
内存消耗：46.8 MB

Python 实现

执行用时：64 ms
内存消耗：17.9 MB

C++ 实现

执行用时：16 ms
内存消耗：13.9 MB

性能对比

语言	执行用时	内存消耗	特点
C#	120 ms	46.8 MB	代码结构清晰
Python	64 ms	17.9 MB	实现简洁
C++	16 ms	13.9 MB	性能最优

代码亮点

🎯 队列实现简单直观
💡 维护总和避免重复计算
🔍 边界条件处理完善
🎨 代码结构优雅

常见错误分析

🚫 忘记更新窗口总和
🚫 平均值计算错误
🚫 队列大小判断错误
🚫 整数除法导致精度损失

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
队列	O(1)	O(size)	实现简单	空间占用大
循环数组	O(1)	O(size)	空间利用率高	实现复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第346题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

提示

解题思路

方法一：队列实现

方法二：循环数组

图解思路

队列实现分析表

循环数组示意图

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流