7.2 队列应用

滑动窗口: 对于数组[1 2 3 4 5 6], 长度为3的窗口[1 2 3], 窗口向右移动一个数字, 最右添加一个元素, 最左边删除一个元素, 变成[2 3 4], 符合先入先出的规则, 可以用队列来表示.

7.2.1 问题41: 滑动窗口平均值

LCR 041. 数据流中的移动平均值

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

实现 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
• -105 <= val <= 105
• 最多调用 next 方法 104 次

7.2.1.1 分析&题解

滑动窗口满足先进先出的规则, 可以使用队列解决.

Golang 中没有队列实现, 可以是使用切片来进行模拟.

窗口中元素的和, 若每次重新计算, 则时间为O(n); 可以利用变量sum缓存上一次的和, 这样每次只需计算一次 $sum+new-old$即可.

type MovingAverage struct {
	queue []int
	size  int
	sum   int
}

func Constructor(size int) MovingAverage {
	return MovingAverage{
		queue: make([]int, 0, size),
		size:  size,
	}
}

func (ma *MovingAverage) Next(val int) float64 {
	var average float64
	// 滑动窗口未满
	if len(ma.queue) < ma.size {
		ma.queue = append(ma.queue, val)
		ma.sum += val
		average = float64(ma.sum) / float64(len(ma.queue))
		return average
	}
	// 滑动窗口已满
	// 队尾出队, 新元素入队
	tail := ma.queue[0]
	ma.queue = ma.queue[1:]
	ma.queue = append(ma.queue, val)
	// 平均值
	ma.sum = ma.sum + val - tail
	average = float64(ma.sum) / float64(len(ma.queue))

	return average
}

7.2.2 问题41: 最近请求次数

LCR 042. 最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例：

输入：
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

• 1 <= t <= 109
• 保证每次对 ping 调用所使用的 t 值都 严格递增
• 至多调用 ping 方法 104 次

7.2.2.1 分析&题解

过去3000ms内的请求, 可以看作是长度为3000的滑动窗口, 新请求到来时计算和队尾的时间差:

• 小于3000ms, 直接入队

• 大于3000ms, 队尾出队, 直到小于为止, 然后入队

type RecentCounter struct {
	queue []int
	size  int
}

func Constructor() RecentCounter {
	return RecentCounter{
		queue: make([]int, 0),
		size:  3000,
	}
}

func (rc *RecentCounter) Ping(t int) int {
	// 空窗口
	if len(rc.queue) == 0 {
		rc.queue = append(rc.queue, t)
		return len(rc.queue)
	}

	// 将超过3000毫秒的请求出队
	for len(rc.queue) > 0 && rc.queue[0]+rc.size < t {
		rc.queue = rc.queue[1:]
	}
	rc.queue = append(rc.queue, t)
	// 返回个数
	return len(rc.queue)
}

和栈应用类似, 连续出队时要搞清楚出队的条件.

Reference

1. 剑指Offer（专项突破版）