平均大于或等于k的最长连续子线

Question

考虑一个由 N 个整数组成的数组。找到最长的连续子数组，使其元素的平均值大于（或等于）给定数字 k。

显而易见的答案具有O（n^2）复杂度。我们能做得更好吗？

Answer 1

我们可以在O（n）时间和O（n）空间复杂度下解决问题：
我已经尝试了朴素和最优的方法。
简而言之，这个问题涉及两个步骤：
（1）从每个ar[i]中减去k，并在新数组中找到累加值。让我们将新数组称为CumArr[]。
（2）现在问题变成了在CumArr[]中找到max（j-1）使得j

下面是运行代码的详细信息：http://codeshare.io/Y1Xc8

可能会有一些小的角落案件可以很容易地处理。
朋友们，让我知道你的想法。

Answer 2

我们可以将这个问题简化为最长的连续子数组，总和

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找到相距最远的两个索引

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

现在，让我们回到原来的前缀数组。对于每个前缀-索引对，我们在新的数组上做一个二分搜索法来找到最小的前缀

由于排序和n次二进制搜索，该算法是O(n log n)。