# 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

```java
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

```java
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

```java
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);
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/data-structure/346.moving-average-from-data-stream.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.