题目

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

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

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

解题思路：如果进行排序，这里会超时。采用桶排序 排序算法 的思想，可以在线性时间解决。

1. 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。
2. 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。
3. 确定桶的数量，最后的加一保证了数组的最大值也能分到一个桶。为什么需要这样规定桶的尺寸呢？因为这样可以让最大的间距的两个元素在两个不同的桶中。可以证明一下，因为我们用元素范围之差除以元素个数，所以桶的尺寸就是平均的元素间距，显然最大间距的两个元素不可能在同一个桶。为什么要最大间距的元素在两个不同的桶中呢？如果两个元素在桶中，那就又需要再桶中进行排序求解了，这样桶排序的优势就没了。
4. 遍历数组，把元素放到桶中。这里只需要一个桶中元素的最大值和最小值，因为答案不会在一个桶中，所以，只需要比较相邻桶的边界就能获取答案，其余的值只会碍事。
5. 遍历桶，用当前桶的最小值减去上一个桶的最大值，就是可能的答案。

举个例子

```plain text nums = [1,3,4,5,6,10,11,12,17] 每个桶的长度 = （17 - 1） / (9-1) = 2 桶的个数 = （17-1）/ 2 + 1 = 9 所以我们的桶为（左闭右开）： | 区间 | [1,3) | [3,5) | [5,7) | [7,9) | [9,11) | [11,13) | [13,15) | [15,17) | [17,19) | |------|-------|-------|-------|-------|--------|---------|---------|---------|---------| | 元素 | 1 | 3,4 | 5,6 | | 10 | 11,12 | | | 17 |

**代码**

```python
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0

        # 一些初始化
        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0

        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]

        # 把数字放入桶中
        for i in range(len(nums)):
            loc = (nums[i] - min_) // each_bucket_len
            buckets[loc].append(nums[i])

        # 遍历桶更新答案
        prev_max = float('inf')
        for i in range(len(buckets)):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i])-prev_max)

            if buckets[i]:
                prev_max = max(buckets[i])

        return max_gap