Question

Formatted question description: https://leetcode.ca/all/346.html

 346	Moving Average from Data Stream

 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

 @tag-design
 @tag-stream

Algorithm

This first-in, first-out feature is most suitable for using queues, and we also need a double variable sum to record the sum of all current numbers.

After entering this new number,

• If the limit is not exceeded, sum plus this number,
• If it exceeds, then sum first subtracts the earliest number, then adds this number, and then returns the number of sum divided by the queue

Code

Java

import java.util.LinkedList;

public class Moving_Average_from_Data_Stream {

    public static void main(String[] args) {
        Moving_Average_from_Data_Stream out = new Moving_Average_from_Data_Stream();
        MovingAverage m = out.new MovingAverage(3);

        System.out.println(m.next(1));
        System.out.println(m.next(10));
        System.out.println(m.next(3));
        System.out.println(m.next(5));
    }

    public class MovingAverage {
        LinkedList<Integer> queue;
        int size;
        double avg;

        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.queue = new LinkedList<Integer>();
            this.size = size;
        }

        /** API: Return moving average. */
        public double next(int val) {
            if (queue.size() < this.size) {
                queue.offer(val);
                int sum = 0;
                for (int i : queue) {
                    sum += i;
                }
                avg = (double) sum / queue.size();

                return avg;
            } else {
                int head = queue.poll();
                queue.offer(val);

                double minus = (double) head / this.size;
                double add = (double) val / this.size;

                avg = avg + add - minus; // math

                return avg;
            }
        }
    }
}

All Problems

All Solutions