LCR041. 滑动窗口的平均值

题目描述：

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

实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

测试用例：

示例 :

输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]
解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

限制及提示：

• 1 <= size <= 1000
• -10^5 <= val <= 10^5
• 最多调用 next 方法 10^4 次

---

解题分析及思路：

滑动窗口的题目通常可以用数组或者队列来进行解决。

那么本题就采用数组的形式。

在本题中，只关心size范围内的数值，那么我们可以初始化一个大小为size的切片。

又因为他需要获得size范围内的数值的总和，则需要定义一个sum的变量来保存总值。

这时候就该看限制了。

• 1 <= size <= 1000
• -10^5 <= val <= 10^5

就算极限值1000个10^5大小的数进行相加也并不会超过int的表示范围，所以sum可以大胆的使用int来表达。

那么有了总和，怎么计算当前的值呢？

可以看到示例中，如果保存在切片内的数量小于size，那么实际按保存的数量来计算，否则按size来计算。所以还需要一个变量来保存当前已经保存的数量。

代码分析：

定义MovingAverage结构体，并编写初始化函数 ：

type MovingAverage struct {
	// 保存数量
	num  int
	// 总值
	sum  int
	nums []int
}

/** Initialize your data structure here. */
func Constructor(size int) MovingAverage {
	return MovingAverage{
		0,
		0,
		make([]int, size),
	}
}

通过当前this.num来计算当前元素val需要保存的下标位置，并且对总数sum进行计算，淘汰（减去）上一个待在当前位置的元素值，再加上当前值。

再通过this.num与 size也就是len(this.nums)的比较返回最终值。

func (this *MovingAverage) Next(val int) float64 {
	index := this.num % len(this.nums)
	this.sum -= this.nums[index]
	this.sum += val
	this.nums[index] = val
	this.num++
	if this.num < len(this.nums) {
		return float64(this.sum) / float64(this.num)
	}
	return float64(this.sum) / float64(len(this.nums))
}

复杂度：

• 时间复杂度：O(1)
• 空间复杂度：O(size)

执行结果：

• 执行用时： 12 ms , 在所有 Go 提交中击败了 95.09% 的用户
• 内存消耗： 7.6 MB , 在所有 Go 提交中击败了 12.50% 的用户