Easy to understand solution (beats 90% with explanations)


  • 0

    The main idea is to keep the last sum and the last index. Use a list to hold the value which only takes O(1) to get the "nonfunctional" value by the last index. Deduct the nonfunctional value and plus the new value will generate the new sum.

    public class MovingAverage {
        private int size;
        private List<Integer> list = new ArrayList<Integer>();
        private int lastSum;
        private int lastIndex;
    
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.size = size;
            lastIndex = -1;
        }
        
        public double next(int val) {
            list.add(val);
            if (lastIndex < 0) {
                lastIndex = 0;
                lastSum = val;
                return (double)val;
            }
            if (list.size() <= size) {
                lastSum += val;
                return (double)lastSum / list.size();
            } else {
                lastSum = lastSum - list.get(lastIndex++) + val;
                return (double)lastSum / size;
            }
            
        }
    }
    

Log in to reply
 

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