My Java Solution with ArrayDeque


  • 0
    I

    Use an ArrayDeque to hold numbers.
    Set a variable tmp to be the placeholder and update it when next() is called.
    Once the size of ArrayDeque is larger than the window.
    Then poll() the current head out and also update the tmp.

    class MovingAverage {
    
        Deque <Integer> moveAvgDQ;
        int size;
        double tmp;
    
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.moveAvgDQ = new ArrayDeque <> (size);
            this.size = size;
        }
        
        public double next(int val) {
            
            if(moveAvgDQ.size()>=this.size){
                tmp-= moveAvgDQ.poll();
                moveAvgDQ.offer(val);
            }else{
                moveAvgDQ.offer(val);
            }
            tmp+=val;
    
            return tmp/moveAvgDQ.size();
        }
    }
    

    Time Complexity: O(1)
    Space Complexity: O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.