1

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

如果没有可能的解决方案，则返回 -1。

例子 ：

A : [3 5 4 2] 输出 : 2 对 (3, 4)

输入： 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 个循环，它通过了上述情况，但为另一个提供了 Time Limit Exceed。

        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
4

2 回答 2

2

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

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

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

  1. Arg 排序输入数组a。在计算机科学中，arg-sort 意味着找到使数组排序的索引顺序。换句话说，如果我有数组a，那么 arg-sort 会找到索引数组，sort_idxs以便数组a[sort_idxs[i]]对 all 进行排序0 <= i < len(a)。这一步是通过带有提供参数的常规sorted()内置函数完成的。key = lambda...

  2. 查找 arg-sort 索引的反向，即查找索引数组，sort_idxs_rev使得sort_idxs_rev[sort_idxs[i]] = i所有0 <= i < len(a). 该步骤在时间上是线性的，即需要O(N)时间。

  3. 设置begin_k和max_dist都保持 value 0。向后遍历所有j范围。0 <= j < len(a)迭代时，执行 steps 4.-5.。步骤4.-5.需要线性时间O(N)。

  4. i找到所有范围内sort_idxs[k]的最小值（表示为） 。kbegin_k <= k < sort_idxs_rev[j]

  5. 更新，这是产生的最大距离，如果它大于先前的值，则max_dist更新它以保持新值。更新持有。j - imax_distbegin_ksort_idxs_rev[j] + 1

  6. 输出结果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).

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

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

j当我们从右到左迭代所有内容时，这意味着我们观察jthis 的每个最大可能距离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-loop 的总运行时间是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 的每个访问者都可以在没有外部依赖的情况下运行。最终答案打印到控制台输出。

完整代码如下：

在线尝试！

# 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

输出：

2
于 2021-11-22T20:40:33.533 回答
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
于 2021-11-22T18:24:48.677 回答