为什么此代码未通过测试用例 [最大距离]

Question

问题：给定一个整数数组A，在A[i]的约束下求j - i的最大值<= A[j].

如果无解，return-1.

示例：

一个：[3 5 4 2] 输出：对 (3, 4)

为 2

输入： 9 8 7 -9 -1

预期输出： 1

我的输出： 0

我尝试运行的代码适用于除上述给定输入以外的所有情况，谁能解释为什么这种情况失败并向我提供修正后的版本？

我的代码(Python):

class Solution:
    def maximumGap(self, A):
        # write your method here
        m=-1
        for i in range(len(A)-1):
            j=len(A)-i-1
            if(A[i]<=A[j]):
                m=max(m,j-i)
        return m

我尝试使用 2 个循环，它通过了上述情况，但给另一个循环超过了时间限制。

        m=-1
        for i in range(len(A)):
            for j in range(len(A)): 
                if(A[i]<=A[j]):
                    m=max(m,j-i)
        return m

Answer 1

您不需要测试每一对。从末尾搜索，直到找到 >= 当前元素的元素，这将是最大的差距。

作为额外的优化，您可以保存该元素的 j 值，并在通过它时跳出外循环。

m = -1
maxj = len(A)
for i, el in enumerate(A):
    if i > maxj:
        break
    for j in range(len(A)-1, -1, -1):
        if el <= A[j]:
            m = max(m, j-i)
            maxj = j
            break

Answer 2

你的问题很有趣！我受到它的启发，实施了非常快速、几乎线性的时间解决方案。我下面的算法使用排序并且运行ning 时间由整个数组的单次排序速度决定，所以它有运行ning 时间 O(N * Log2(N)) 其中 N 是数量数组中的元素。

尽管我的算法比其他解决方案更复杂，但与具有运行时间 O(N^2) 的其他二次解决方案相比，它实现了更大 N 更快的速度，其中一个OP的问题中提供了二次解。

在我的算法中，我们执行以下步骤：

Arg 排序输入数组 a。在计算机科学中，arg-sort 意味着找到使数组排序的索引顺序。换句话说，如果我有数组 a，那么 arg-sort 会找到索引数组 sort_idxs，这样数组 a[sort_idxs[i]] 就会对所有 0 <= i < len(a) 进行排序。此步骤是通过带有提供的 key = lambda... 参数的常规 sorted() 内置函数完成的。
查找 arg-sort 索引的反向，即找到索引数组 sort_idxs_rev，使得所有 0 <= i < len(a) 的 sort_idxs_rev[sort_idxs[i]] = i。此步骤在时间上是线性的，即需要 O(N) 时间。
设置 begin_k 和 max_dist 都保持值 0。向后遍历 0 <= j < len(a) 范围内的所有 j。迭代时，执行步骤 4.-5.。步骤 4.-5. 需要线性时间 O(N)。
在 begin_k <= k < sort_idxs_rev[j].
范围内找到 k 的所有 sort_idxs[k] 的最小值（表示为 i）
更新 max_dist，这是最大距离，如果它比之前的 max_dist 大，则更新它以保持新值 j - i。更新 begin_k 以保留 sort_idxs_rev[j] + 1。
输出结果 max_dist 作为答案。

上面算法的解释：

可以观察到如果我们取最右边的值 a[j] 那么对于所有 a[i] <= a[j] 我们可以将最大距离更新为 j - "(minimal such i)" 如果最大距离更小（并且最大距离是 0 在开始时）。

之后我们可以从进一步的计算中删除数组元素 a[i] 使得 a[i] <= a[j]，因为没有其他更小的 j 会为所有 a[i] 提供更大的距离a[i] <= a[j]。如果其他一些 j0 这样 j0 < j 会给出更大的距离，这将意味着 j - min_i < j0 - min_i，因此 j < j0 但我们采用 j0 这样 j0 < j因此矛盾。

在 i 个索引中找到最小元素需要线性时间 O(count_i)，而且由于这些 i 已从进一步计算中删除，这意味着后续步骤将花费 O(N - count_i) 时间, 因此总时间为 O(count_i) + O(N - count_i) = O(N).

我们可以使用先前计算的 arg-sort 和反向 arg-sort 索引找到所有小于 a[j] 的元素。因此，寻找更小的元素在时间上是线性的。

所以每个j删除一堆a[i]小于a[j]的元素。它还将最大距离更新为最大可能的 j.

当我们从右到左迭代所有 j 时，这意味着我们观察每个 j 这个 j 的最大可能距离。所有 j 的所有最大距离的最大值将是最终解决方案，因为如果存在解决方案则意味着它在某个 j = j_sol 点实现，但因为我们观察了所有 j 然后这意味着我们还观察到 j = j_sol 及其相应的最大距离答案。

在 j 的每次迭代中，我们删除了一堆 a[i]，我们将它们从进一步观察中删除。这意味着在每次迭代中数组变得越来越短。每次迭代都需要线性时间 O(count_i) 来找到最小的 i，其中 count_i 是移除的 i 索引的数量。由于每次迭代删除相同数量 count_i 并花费时间 O(count_i) 找到最小值，因此 j 循环的总运行时间为 O(count_i_0) + ... + O(count_i_N) = O(N)，因为所有 count_i等于N总和

当然，实际上删除数组元素 a[i] 会很慢，因为 Python 的列表的实现方式是删除列表中间的元素需要很多时间，实际上O(N) 时间。所以在我下面的代码中，我没有实际删除元素，而是在每次迭代中将 begin_k 增加 count_i，这样我模拟删除元素，因为从排序数组中删除元素只是意味着保留一些指向范围的开始，直到这个指针一切都被认为是“已删除”，因此我保留这样的 begin_k（逐渐增长 count_i），它表示排序数组中的一个点，在此之前一切都是视为已删除。

所以 arg-sort 花费了大部分时间，仍然非常非常快，O(N * Log2(N))，因为 Python 中的排序是在这段时间内实现的。反向 arg-sort 采用 O(N)。然后 j 循环的总时间也需要 O(N)。因此，总运行宁时间主要由排序算法的速度决定。

如果输入数组真的非常大，比如数十亿个元素，那么我的算法将击败 O(N^2) 运行宁时间的所有二次算法。当然，要处理数十亿的数组元素，必须使用 C++ 而不是 Python。在 C++ 中对数十亿个元素进行排序仍然很快，并且需要十几秒。

在我的代码中，如果您想从控制台获取输入，可以将第一行从 input_ = '3 5 4 2' 更改为 input_ = input()。 3 5 4 2 在代码中用作固定输入只是为了运行能够独立的示例，Stack-Overflow 的每个访问者都可以运行而无需外部依赖。最终答案打印到控制台输出。

完整代码如下：

Try it online!

# Input data
#input_ = '9 8 7 -9 -1'
input_ = '3 5 4 2' # input()
a = list(map(int, input_.split()))

# Arg-sort input array
sort_idxs = sorted(range(len(a)), key = lambda i: (a[i], i))

# Compute reverse of arg-sort indices
sort_idxs_rev = [0] * len(a)
for i0, i1 in enumerate(sort_idxs):
    sort_idxs_rev[i1] = i0
    
begin_k = 0
max_dist = 0

# Linearly search for the answer
for j in range(len(a) - 1, -1, -1):
    end_k = sort_idxs_rev[j]
    if begin_k >= end_k:
        continue
    i = min(sort_idxs[k] for k in range(begin_k, end_k))
    max_dist = max(max_dist, j - i)
    begin_k = end_k + 1
    if begin_k >= len(a):
        break

# Output answer
print(max_dist)

输入：

3 5 4 2

输出：

为什么此代码未通过测试用例 [最大距离]

Why is this code failing a test case [Max Distance]

python

arrays

prefix-sum