平均大于或等于k的最长连续子数组 [英] Longest Contiguous Subarray with Average Greater than or Equal to k

问题描述

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

Consider an array of N integers. Find the longest contiguous subarray so that the average of its elements is greater (or equal) than a given number k.

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

The obvious answer has O(n^2) complexity. Can we do better?

推荐答案

我们可以通过从所有值中减去k来将这个问题减少为最长连续子数组，其和> = 0在O（n）时间内。现在让我们计算前缀总和：

We can reduce this problem to longest contiguous subarray with sum >= 0 by subtracting k from all values in O(n) time. Now let's calculate prefix sums:

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 。让我们创建一个新的prefix-index数组，并按前缀对它们进行排序，然后对索引进行排序。

Now this problem is finding the two indices most far apart with prefix_right - prefix_left >= 0. Let's create a new prefix-index array and sort it by prefix, then indices.

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

然后我们可以对左扫以为每个前缀计算前缀大于或等于当前前缀的最大索引：

We can then do a right-to-left sweep to calculate, for each prefix, the maximum index with prefix greater than or equal to the current prefix:

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中减去当前前缀的索引，以检索从当前索引开始的最佳可能序列长度。取最大长度的序列。

Now, let's go back to the original prefix array. For each prefix-index pair, we do a binary search on our new array to find the smallest prefix >= the current prefix. We subtract, from maxind of the binary searched prefix, the index of the current prefix to retrieve the best possible sequence length starting at the current index. Take the sequence with the maximum length.

由于排序和n个二进制搜索，该算法为O（n log n）。

This algorithm is O(n log n) because of the sorting and the n binary searches.

这篇关于平均大于或等于k的最长连续子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！