164. 最大间距

https://leetcode-cn.com/problems/maximum-gap/

解法一：桶方法

由鸽巢原理，将n个数之间的n-1个间隔平均等分，每个间隔为gap = ceil((max-min)/(n-1))，则最大间隔不会小于这个平均间隔，每个间隔作为一个桶。

记最小最大值为min，max。将数组中的所有数划分到n-1个桶，用i = (num-min)/gap来确定num划分在i号桶中（i=0~n-2）。由于每个桶的容量为gap = ceil((max-min)/(n-1))，因此桶中元素的最大间隔不会超过gap。找最大间距只需要找桶与桶之间的元素间距。进而推出只需要记录桶中最大与最小元素即可，中间的不需要考虑。

用一个bucketsMin数组存放所有桶的最下元素，bucketsMax存放最大。从0号桶开始到n-2号，每次计算并更新maxGap = i桶的最小值 与 i-1桶（前一个桶）的最大值的差值。注意初始桶是与min比较，最后一个桶是与max比较。

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        minNum = maxNum = nums[0]
        #找最大最小值
        for num in nums:
            minNum = min(minNum, num)
            maxNum = max(maxNum, num)
        #计算桶大小
        gap = math.ceil((maxNum - minNum) / (n-1))
        #存放所有桶的最小值和最大值
        bucketsMin = [sys.maxsize] * (n-1)
        bucketsMax = [-sys.maxsize] * (n-1)
        #填充桶
        for num in nums:
            if num == minNum or num == maxNum:
                continue
            #计算num应该划分的桶序号
            idx = (num - minNum) // gap
            #更新
            bucketsMin[idx] = min(bucketsMin[idx], num)
            bucketsMax[idx] = max(bucketsMax[idx], num)
        
        pre = minNum  #前一个桶的最大值
        maxGap = -sys.maxsize  #最大间隔
        #遍历所有桶
        for i in range(len(nums)-1):
            #若是空桶
            if bucketsMin[i] == sys.maxsize and bucketsMax[i] == -sys.maxsize:
                continue
            maxGap = max(maxGap, bucketsMin[i] - pre)
            pre = bucketsMax[i]
        #最后与max比较
        maxGap = max(maxGap, maxNum - pre)
        return maxGap