最大间距

题目链接

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

思路

解法一：

使用基数排序数组，取相邻元素最大的值

  • 基数排序重点：对位数元素排序算法要求必须是稳定的
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        nums = self.radixSort(nums)
        return max(nums[i] - nums[i - 1] for i in range(1, len(nums)))

    def radixSort(self, nums):
        for i in range(len(str(max(nums)))):
            buckets = [[] for _ in range(10)] # 创建十进制的二维数组
            for num in nums: # 按照位数的值进行添加到对应的bucket
                buckets[num // (10 ** i) % 10].append(num)
            nums.clear()
            for bucket in buckets: # 按照bucket进行排序
                for num in bucket:
                    nums.append(num)
        return nums