问题描述
给定一个无序数组，求排序后数组中的最大间隔。例如给定数组 [2, 9, 7, 6] 的最大间隔 为 4，因为排序后数组为 [2, 6, 7, 9]，间隔分别为 [4, 1, 2]。
要求：时间复杂度为O(n)
求解
如果不考虑时间复杂度的话，可以直接对数组进行排序，然后遍历数组求出最大间隔即可。
若要时间复杂度为 O(n) 只能用空间来换时间，考虑分桶做法。首先需要遍历一遍数组，获取数组的最大值、最小值：min_n, max_n = min(nums), max(nums)。然后遍历数组，将数字放入对应的桶中。
将 n 个数放到 n+1 个桶中：index = (num - min_n) * n / (max_n - min_n)，这样就把数组放到了下标为 0~n 的 n-1 个桶中，且最小值、最大值分别放在第一个与最后一个桶中。如此一来，最大间隔必由空桶两侧的桶得出。
完整代码如下所示：
if not nums or len(nums) == 0:
return 0
min_n, max_n, len_n = min(nums), max(nums), len(nums)
but_min, but_max = [float('inf')] * (len_n + 1), [-float('inf')] * (len_n + 1)
if max_n == min_n:
return 0
for n in nums:
index = (n - min_n) * len_n // (max_n - min_n)
if n < but_min[index]:
but_min[index] = n
if n > but_max[index]:
but_max[index] = n
i, res = 0, -1
while i < len_n:
if but_min[i+1] != float('inf'):
i += 1
continue
j = i + 1
while j < len_n+1 and but_min[j] == float('inf'):
j += 1
if j < len_n+1:
res = max(res, but_min[j] - but_max[i])
i = j
return res