346.Moving Average from Data Stream

Tags: [stream], [streaming], [average], [queue], [iterator], [data_structure]

Com: {g}

Link: https://leetcode.com/problems/moving-average-from-data-stream/\#/description

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,

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

Solution: Queue

from collections import deque

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.queue = deque()


    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        if len(self.queue) == self.size:
            self.queue.popleft()
        self.queue.append(val)

        return float(sum(self.queue)) / float(len(self.queue))


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Revelation:

• When we talk about the streaming, we should always think about there is a time window. And when we discuss the streaming, which should always be based on time window.

Note:

• Time complexity of initialization = O(1).
• Time complexity of next = O(size).