Sword finger offer II 041 Average value of sliding window

A word summary

Using queue implementation , Ensure that the queue length is the size of the sliding window . That is, the element is removed from the front of the queue after it exceeds .

subject

Given an integer data stream and a window size , Depending on the size of the sliding window , Calculate the average of all numbers in the sliding window .

Realization MovingAverage class ：

MovingAverage(int size) Use window size size Initialize object .

double next(int val) Member functions next An integer will be added to the sliding window every time , Please calculate and return the last... In the data stream size Moving average of values , That is, the average of all numbers in the sliding window .

link ：https://leetcode.cn/problems/qIsx9U

Ideas

That is to say , The window size is fixed , When the number of elements in the window is less than the window size , Add integers to the window , And calculate the average value directly .

If you add an integer , The number exceeds the window size , You need to eliminate the first element .

fifo , That's the queue .

solution ： Using the queue

Code

public class MovingAverage {
    
    Queue<Integer> queue = new LinkedList<>();
    int maxSize;
    int size;
    int total;

    /** * Initialize your data structure here. */
    public MovingAverage(int size) {
    
        maxSize = size;
    }

    public double next(int val) {
    
        //  Current value is queued 
        queue.add(val);
        total += val;
        if (size >= maxSize) {
    
            Integer poll = queue.poll();
            total = total - poll;
        } else {
    
            size++;
        }
        return (double) total / (double) size;
    }
}

Submit results

Expand your knowledge ： queue

Commonly used api

queue , First in, first out .

Java The queue in , Need to achieve Queue This interface .

Commonly used api The definition of ：

• boolean offer(E e) Add elements at the end of the team . If there is not enough space, return false.
• E poll() The team leader removes the element . If the queue is empty , Then return to null.
• E peek() Get team leader elements , Do not remove . If the queue is empty , Then return to null.
• boolean add(E e) Add elements at the end of the team . If there is not enough space, an exception will be thrown .
• E remove() The team leader removes the element . If the queue is empty , Throw an exception
• E element() Get team leader elements , Do not remove . If the queue is empty , Throw an exception

We often use the implementation , It's all used LinkedList To achieve Queue. And because LinkedList It's a chain , Therefore, it does not involve the limitation of space ,offer The implementation of a method is essentially a call add Method .