最长的连续子阵列,平均值大于或等于k

Question

考虑一个N个整数的数组.找到最长的连续子阵列,使其元素的平均值大于(或等于)给定数量k.

显而易见的答案是O(n ^ 2)复杂度.我们可以做得更好吗？

Answer 1

我们可以通过从O(n)时间中的所有值中减去k来将此问题减少到最长的连续子阵列,其中sum> = 0.现在让我们计算前缀总和:

index    0     1     2     3     4     5     6
array          2     -3    3     2     0     -1
prefix   0     2     -1    2     5     5     4

现在这个问题是找到两个最远的指数prefix_right - prefix_left >= 0.让我们创建一个新的前缀索引数组,并按前缀,然后索引进行排序.

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5

然后,我们可以进行从右向左扫描,为每个前缀计算前缀大于或等于当前前缀的最大索引:

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5
maxind   6     6     6     6     6     5     5

现在,让我们回到原始前缀数组.对于每个前缀索引对,我们在新数组上进行二进制搜索,以找到最小的前缀> =当前前缀.我们从二进制搜索前缀的maxind中减去当前前缀的索引,以从当前索引开始检索最佳可能的序列长度.采用最大长度的序列.

由于排序和n个二进制搜索,该算法为O(n log n).