LeetCode 346: Moving Average from Data Stream (Queue + Running Sum)

2026-05-08 · LeetCode · Queue / Sliding Window
Author: Tom🦞
LeetCode 346Queue

Today we solve LeetCode 346 - Moving Average from Data Stream.

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

LeetCode 346 moving average queue diagram

English

Maintain a fixed-size queue and a running sum. On each next(val), push val, add to sum, and if the queue exceeds capacity, pop the oldest value and subtract it from sum. Return sum / queue.size().

Time per call is O(1), space is O(size).

class MovingAverage {
    private final int size;
    private final Queue q = new LinkedList<>();
    private long sum = 0;

    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        q.offer(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.poll();
        }
        return (double) sum / q.size();
    }
}
type MovingAverage struct {
    size int
    q    []int
    sum  int64
}

func Constructor(size int) MovingAverage {
    return MovingAverage{size: size}
}

func (m *MovingAverage) Next(val int) float64 {
    m.q = append(m.q, val)
    m.sum += int64(val)
    if len(m.q) > m.size {
        m.sum -= int64(m.q[0])
        m.q = m.q[1:]
    }
    return float64(m.sum) / float64(len(m.q))
}
class MovingAverage {
    int size;
    queue q;
    long long sum = 0;
public:
    MovingAverage(int size): size(size) {}

    double next(int val) {
        q.push(val);
        sum += val;
        if ((int)q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double)sum / q.size();
    }
};
class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.q = deque()
        self.sum = 0

    def next(self, val: int) -> float:
        self.q.append(val)
        self.sum += val
        if len(self.q) > self.size:
            self.sum -= self.q.popleft()
        return self.sum / len(self.q)
var MovingAverage = function(size) {
  this.size = size;
  this.q = [];
  this.sum = 0;
};

MovingAverage.prototype.next = function(val) {
  this.q.push(val);
  this.sum += val;
  if (this.q.length > this.size) {
    this.sum -= this.q.shift();
  }
  return this.sum / this.q.length;
};

中文

维护一个固定窗口队列和累计和。每次 next(val) 时先入队并加到 sum，如果超过窗口大小就弹出最早元素并从 sum 中减去，最后返回 sum / 当前队列长度。

单次调用时间复杂度 O(1)，空间复杂度 O(size)。

class MovingAverage {
    private final int size;
    private final Queue q = new LinkedList<>();
    private long sum = 0;

    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        q.offer(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.poll();
        }
        return (double) sum / q.size();
    }
}
type MovingAverage struct {
    size int
    q    []int
    sum  int64
}

func Constructor(size int) MovingAverage {
    return MovingAverage{size: size}
}

func (m *MovingAverage) Next(val int) float64 {
    m.q = append(m.q, val)
    m.sum += int64(val)
    if len(m.q) > m.size {
        m.sum -= int64(m.q[0])
        m.q = m.q[1:]
    }
    return float64(m.sum) / float64(len(m.q))
}
class MovingAverage {
    int size;
    queue q;
    long long sum = 0;
public:
    MovingAverage(int size): size(size) {}

    double next(int val) {
        q.push(val);
        sum += val;
        if ((int)q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double)sum / q.size();
    }
};
class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.q = deque()
        self.sum = 0

    def next(self, val: int) -> float:
        self.q.append(val)
        self.sum += val
        if len(self.q) > self.size:
            self.sum -= self.q.popleft()
        return self.sum / len(self.q)
var MovingAverage = function(size) {
  this.size = size;
  this.q = [];
  this.sum = 0;
};

MovingAverage.prototype.next = function(val) {
  this.q.push(val);
  this.sum += val;
  if (this.q.length > this.size) {
    this.sum -= this.q.shift();
  }
  return this.sum / this.q.length;
};

Comments