Maximum Gap——无序数组中，排序后相邻的两个数，差值最大为多少

 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 0
10             
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 0
17         
18         # 最后的的答案一定大于等于 bucket_size
19         # 因为只有这n个数均匀排列才等于bucket_size
20         # 否则一定大于bucket_size
21         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, None
34         
35         for cur_bucket in range(len(buckets)):
36             if buckets[cur_bucket] == None:
37                 continue
38             if pre_bucket != None:
39                 ans = max(ans, buckets[cur_bucket][0] - buckets[pre_bucket][1])
40             pre_bucket = cur_bucket
41         
42         return ans