《Leetcode of November》164. 最大间距

 

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

        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0
        
        #桶排序
        #1.每个桶的大小是多少;2.需要几个桶;3.如何把数字排序的放在桶中
        #step1
        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))
        #step2
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]
        
        #step3
        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


        #暴力排序
        nums.sort()
        i,j = 0,1
        res = 0
        while i<len(nums) and j<len(nums):
            res = max(res,nums[j]-nums[i])
            i+=1
            j+=1
        return res

分析

• 暴力法，直接sort然后找最大值
• 桶排序，当前桶的最大和下个桶的最小做差，找出最大的差

总结：通过这个题目学习了桶排序。