一、题目

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

示例:

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

  

 

  
1
  
2
  
3
  
4
  
5
 

二、思路

就是一个滑动窗口的题目，即每次的next(val)操作都会在原来的基础上加入元素，并且将当前滑动窗口内的元素之和除以窗口大小，几个点要注意：
（1）窗口大小虽然给定k，但是不一定是除以k，因为可能当窗口内的元素小于k时。
（2）因为每次的next操作会基于原来的数据，并且后面需要剔除开头的元素，容易想到用队列的数据结构，即如果当队列大小超出k则循环剔除前面的元素，同时更重要的是将sum减去剔除的元素值。

三、代码

class MovingAverage {
	queue<int> q;
	int windowsize;
	int sum = 0;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
    	windowsize = size;
    }
    
    double next(int val) {
    	sum += val;
    	q.push(val);
		if(q.size() > windowsize){
			sum -= q.front();
			q.pop();//队头元素出队
		}
		return sum / double(q.size());
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122592816