164. Maximum Gap: 试了一下bucket sort，好像不太行，看了答案，发现是自己的思路问题，bucket的设定想错的。bucket装的是差值小于最小可能值的值，所以只要存储左边界和右边界就可以了还有一种radix sort的解法，还要研究一下。
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
N = len(nums)
if (N < 2):
return 0
imin = min(nums)
imax = max(nums)
M = max(1, int(1.0 * (imax - imin) / (N - 1))) # 找出max difference的最小可能值
buckets = [None] * ((imax - imin) / M + 1) # 做出buckets，每个bucket之间的差距是M
for x in nums:
i = (x - imin) / M
bucket = buckets[i] # 提取出当前x所在的bucket
if bucket is None:
buckets[i] = {'min': x, 'max': x}
else:
bucket['min'] = min(bucket['min'], x) # 这两步就是设定bucket的边界，左边界和有边界，因为bucket本身也是有长度M的
bucket['max'] = max(bucket['max'], x)
gap = 0
prev = buckets[0]
for i in range(1, len(buckets)):
if buckets[i] is None:
continue
# 因为如果两个值在同一个bucket里面，那么就说明它们的差值小于M，就不可能是解
# 所以要求当前左边界和上一个的有边界之间的差值
gap = max(gap, buckets[i]['min'] - prev['max'])
prev = buckets[i]
return gap
