给定一个未经排序的数组，请找出其排序表中连续两个要素的最大间距。

如果数组中的要素少于 2 个，请返回 0.

给定数组 [1, 9, 2, 5]，其排序表为 [1, 2, 5, 9]，其最大的间距是在 5 和 9 之间，= 4.

---

1 class Solution: 2     """ 3     @param nums: an array of integers 4     @return: the maximun difference 5     """ 6     def maximumGap(self, nums): 7         # write your code here 8         if nums is None or len(nums) < 2: 9             return 010             11         MIN, MAX, n = nums[0], nums[0], len(nums)12         for num in nums:13             MIN, MAX = min(MIN, num), max(MAX, num)14             15         if MIN == MAX:16             return 017         18         # 最后的的答案一定大于等于 bucket_size19         # 因为只有这n个数均匀排列才等于bucket_size20         # 否则一定大于bucket_size21         bucket_size = (MAX - MIN) / (n - 1)22         buckets = [None for i in range(n)]23         24         # 将每个数放到相应的桶内25         for num in nums:26             bucket_id = int((num - MIN) // bucket_size)27             if buckets[bucket_id] == None:28                 buckets[bucket_id] = [num, num]29             else:30                 buckets[bucket_id][0] = min(buckets[bucket_id][0], num)31                 buckets[bucket_id][1] = max(buckets[bucket_id][1], num)32         33         ans, pre_bucket = 0, None34         35         for cur_bucket in range(len(buckets)):36             if buckets[cur_bucket] == None:37                 continue38             if pre_bucket != None:39                 ans = max(ans, buckets[cur_bucket][0] - buckets[pre_bucket][1])40             pre_bucket = cur_bucket41         42         return ans