346.Moving-Average-from-Data-Stream

346. Moving Average from Data Stream

题目地址

https://leetcode.com/problems/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.

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

代码

Approach #1 Array or List

class MovingAverage {

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

  public double next(int val) {
        queue.add(val);
    int windowSum = 0;
    for (int i = Math.max(0, queue.size() - size); i < queue.size(); i++) {
      windowSum += (int)queue.get(i);
    }

    return windowSum * 1.0 / Math.min(queue.size(), size);
  }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

Approach #2 Double-ended Queue

class MovingAverage {
  int size, windowsUM = 0, count = 0;
  Deque queue = new ArrayDeque<Integer>();

  public MovingAverage(int size) {
    this.size = size;
  }

  public double next(int val) {
    count++;
    queue.add(val);
    int tail = count > size ? (int)queue.poll() : 0;

    windowSum = windowSum - tail + val;

    return windowSum * 1.0 / Math.min(size, count);
  }
}

Approach #3 Circular Queue with array

class MovingAverage {
  int size, head = 0, windowSum = 0, count = 0;
  int[] queue;
  public MovingAverage(int size) {
    this.size = size;
    queue = new int[size];
  }

  public double next(int val) {
    ++count;
    // calculate the new sum by shifting the window
    int tail = (head + 1) % size;
    windowSum = windowSum - queue[tail] + val;
    // move on to the next head
    head = (head + 1) % size;
    queue[head] = val;
    return windowSum * 1.0 / Math.min(size, count);
  }
}