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;
}
}
}
}