难度: Medium
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
示例 1:
输入: nums = [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: nums = [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
提示:
1 <= nums.length <= 1050 <= nums[i] <= 109运行时间: 122 ms
内存: 33.6 MB
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
mn, mx = min(nums), max(nums)
d = max(1, (mx - mn) // (n - 1))
size = (mx - mn) // d + 1
buckets = [[-1] * 2 for _ in range(size)]
for x in nums:
i = (x - mn) // d
if buckets[i][0] == -1:
buckets[i][0] = buckets[i][1] = x
else:
buckets[i][0] = min(buckets[i][0], x)
buckets[i][1] = max(buckets[i][1], x)
prev = -1
ans = 0
for i, (a, b) in enumerate(buckets):
if a == -1:
continue
if prev != -1:
ans = max(ans, a - buckets[prev][1])
prev = i
return ans
题解采用了桶排序的思路来解决问题。首先，如果数组长度小于2，直接返回0。计算数组最小值mn和最大值mx。接着计算桶的大小d，这是基于最大值和最小值的差以及数组长度来决定的，确保至少有一个元素在每个桶中。桶的数量计算基于(d + 1)来保证所有值都能放入桶中。每个桶用来存储该桶中的最小值和最大值。遍历数组，将每个元素放入相应的桶并更新该桶的最小值和最大值。最后，遍历所有桶，计算相邻非空桶之间的最大差值，即前一个桶的最大值和后一个桶的最小值之间的差。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0 # 数组长度小于2时，无间距
mn, mx = min(nums), max(nums) # 找到数组的最小值和最大值
d = max(1, (mx - mn) // (n - 1)) # 计算桶的间距
size = (mx - mn) // d + 1 # 计算需要的桶的数量
buckets = [[-1] * 2 for _ in range(size)] # 初始化桶
for x in nums:
i = (x - mn) // d # 计算元素应该放入哪个桶
if buckets[i][0] == -1:
buckets[i][0] = buckets[i][1] = x # 初始化桶
else:
buckets[i][0] = min(buckets[i][0], x) # 更新桶的最小值
buckets[i][1] = max(buckets[i][1], x) # 更新桶的最大值
prev = -1
ans = 0
for i, (a, b) in enumerate(buckets):
if a == -1:
continue # 跳过空桶
if prev != -1:
ans = max(ans, a - buckets[prev][1]) # 计算相邻非空桶间的最大差值
prev = i
return ans # 返回最大间距
这个公式的目的是确保至少有一个元素在每个桶中，并且尽可能使相邻元素之间的间距最大化。公式`(mx - mn) // (n - 1)`计算的是理论上相邻元素的最大可能间距（如果元素均匀分布）。这样，我们可以通过保证每个桶至少包含一个元素（除了最大值和最小值之间可能的空桶），最大化相邻非空桶之间的差值，从而找到最大间距。如果直接按照元素数量均分，桶的数量会等于元素数量，这可能导致每个桶中只有一个元素，从而无法有效利用桶排序优化时间复杂度。
在初始化桶时，每个桶中存储的两个元素分别代表该桶中的最小值和最大值。这是因为最终计算最大间距时，我们关心的是相邻非空桶之间的最大差值，这个差值是由前一个桶的最大值和后一个桶的最小值之间的差计算得来的。因此，为了方便计算这种差值，我们在每个桶中维护一个最小值和一个最大值。
这种方法在处理重复元素时没有特别的考虑或需求。重复元素会被放入同一个桶中，因为它们的值相同。在桶内部，即使存在多个相同的元素，我们仍然更新桶中的最小值和最大值，但对于重复值，这不会改变桶的最小值或最大值。因此，重复元素不影响最终计算相邻非空桶之间的最大差值。桶排序的逻辑保证了即使存在重复元素，也能正确计算出最大间距。