algorithm - 如何在 O(n) 时间内找到向量中的最大间隙？

Question

您将获得高速公路上同一车道上各种汽车的位置，作为向量的双倍，没有特定的顺序。如何在 O(n) 时间内找到相邻汽车之间的最大差距？

似乎一个简单的解决方案是先排序然后检查，但这当然不是线性的。

Answer 1

将向量分成 n+1 个大小相等的桶。对于每个这样的桶，存储最大值和最小值，所有其他值都可以丢弃。由于鸽巢原理，这些部分中至少有一个是空的，因此任一部分中的非最小值/非最大值对结果没有影响。

然后，遍历桶，计算到下一个和前一个非空桶的距离，取最大值；这是最终的结果。

一个 n=5 且值为 5,2,20,17,3 的示例。最小值为 2，最大值为 20 => 存储桶大小为 (20-2)/5 = 4。

Bucket:   2    6    10    14     18     20
Min/Max:   2-5   -    -     17,17  20,20

差异：2-5、5-17、17-20。最大值为 5-17。

Answer 2

我的ipc解决方案的Python实现：

def maximum_gap(l):
    n = len(l)
    if n < 2:
        return 0
    (x_min, x_max) = (min(l), max(l))
    if x_min == x_max:
        return 0
    buckets = [None] * (n + 1)
    bucket_size = float(x_max - x_min) / n
    for x in l:
        k = int((x - x_min) / bucket_size)
        if buckets[k] is None:
            buckets[k] = (x, x)
        else:
            buckets[k] = (min(x, buckets[k][0]), max(x, buckets[k][1]))
    result = 0
    for i in range(n):
        if buckets[i + 1] is None:
            buckets[i + 1] = buckets[i]
        else:
            result = max(result, buckets[i + 1][0] - buckets[i][1])
    return result

assert maximum_gap([]) == 0
assert maximum_gap([42]) == 0
assert maximum_gap([1, 1, 1, 1]) == 0
assert maximum_gap([1, 2, 3, 4, 6, 8]) == 2
assert maximum_gap([5, 2, 20, 17, 3]) == 12

如果为空，我使用tuplefor 存储桶的元素。None在最后一部分中，我通过将任何剩余的空桶分配给前一个来抢先消除任何剩余的空桶（这是可行的，因为第一个保证是非空的）。

请注意所有元素都相等的特殊情况。