找到长度至少为k的最大平均子数组

Question

我有一个数组 a1, a2, a3, ...., an (n > 0) 和整数 k (0 < k <= 10^5). Finding optimize the max average subarray with a length of at least k?

输入： 6 2 5 1 7 1 8 2

输出 3 5

解释： [7, 1, 8] 是我们可以拥有的最大平均子数组。

我想知道解决该问题的最佳算法。

Answer 1

我们可以二分查找

O(n log(range of values))

中最大的子数组平均值。

在二分查找的每次迭代中，我们可以检查是否存在线性时间内平均值至少为

mid

的子数组。让

pre[r]

表示数组中直到索引

r

的前缀和。我们要搜索的条件相当于寻找两个索引

l < r

，使得

(pre[r] - pre[l]) / (r - l) >= mid

。

重新整理一下，这是

pre[r] - r * mid >= pre[l] - l * mid

。然后，我们只需要在向前迭代数组的同时计算每个索引的

pre[i] - i * mid

，并维护在当前索引之前至少

k

的索引中遇到的该表达式的最小值。一旦

pre[i] - i * mid

的当前值大于或等于迄今为止的最小值，我们就有了一个平均值至少为

mid

的子数组，并且可以继续在更高的范围内搜索。