本文共 1645 字，大约阅读时间需要 5 分钟。

O(N)的复杂度，运用桶排序（代码1）。但是取巧的方法（代码2）居然24ms，100%。应该是测试数据集设置得不好

class Solution():    def maximumGap(self, nums):        """        :type nums: List[int]        :rtype: int        """        import math        if len(nums) <= 1 :            return 0                        minValue = 2**31-1        maxValue = -2**31        for num in nums:            minValue = min(minValue, num)            maxValue = max(maxValue, num)                        bucket_range = (maxValue - minValue) / len(nums) + 1        bucket_num = math.ceil((maxValue - minValue) / bucket_range) + 1                hashmapMax = {
   }        hashmapMin = {
   }        for i in range(len(nums)):            bucket_id = (nums[i]-minValue) // bucket_range            if not bucket_id in hashmapMax:                hashmapMax[bucket_id] = nums[i]                hashmapMin[bucket_id] = nums[i]            else:                                hashmapMax[bucket_id] = max(hashmapMax[bucket_id],nums[i])                hashmapMin[bucket_id] = min(hashmapMin[bucket_id],nums[i])                    prev = 0        res = 0                for i in range(1,bucket_num):            if not i in hashmapMax:                continue            if not prev in hashmapMax:                continue            res = max(res, hashmapMin[i] - hashmapMax[prev])            prev = i        return res

class Solution(object):    def maximumGap(self, nums):        """        :type nums: List[int]        :rtype: int        """        ln=len(nums)        if ln<2:            return 0         nums.sort()        res=0        for i in range(ln-1):            res=max(res,nums[i+1]-nums[i])        return res

转载地址：http://zwahj.baihongyu.com/