给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/maximum-gap 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述：

给定一个无序的数组 nums，返回数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。

要求：

你必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例：

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

解题思路：

要求线性时间和空间，可以想到桶排序。首先遍历一遍数组，找到最大值和最小值，确定桶的大小和数量。将元素按照一定的规则放入桶中，然后在桶内寻找相邻元素之间的最大差值。

由于题目要求相邻元素之间的最大差值，因此可以将桶的大小设为 max(1, (max-min)/(n-1))，其中 n 为数组的长度，这样可以保证桶内相邻元素之间的差值不会超过桶的大小。

放入桶中的规则可以是：假设桶的数量为 n，那么第 i 个元素所在的桶的编号为 (num[i]-min) * n / (max-min)，这样就可以保证相邻元素在同一个桶中，而不同的桶之间一定存在空桶。

放入桶中后，从左到右依次遍历桶，用当前桶的最小值减去前一个桶的最大值，得到相邻元素之间的差值，取最大值即可。

Python代码实现：

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        
        # 找到最大值和最小值
        max_num, min_num = max(nums), min(nums)
        # 计算桶的大小和数量
        bucket_size = max(1, (max_num - min_num) // (n - 1))
        bucket_num = (max_num - min_num) // bucket_size + 1
        
        # 初始化桶
        bucket = [[float('inf'), float('-inf')] for _ in range(bucket_num)]
        for num in nums:
            # 计算元素所在的桶的编号
            idx = (num - min_num) // bucket_size
            # 更新桶的最大值和最小值
            bucket[idx][0] = min(bucket[idx][0], num)
            bucket[idx][1] = max(bucket[idx][1], num)
        
        # 遍历桶，计算相邻元素之间的最大差值
        res, pre_max = 0, bucket[0][1]
        for i in range(1, bucket_num):
            if bucket[i][0] == float('inf'):
                continue
            res = max(res, bucket[i][0] -