164.md

Maximum Gap

Description

link

---

Solution

首先申明一个定论，那就是假设nums当中最大最小值分别为mx，mi，那么我们假设一个size为ceiling[(max - min) / (N - 1)]，在最多为均匀分布的情况下，Maximum Gap为size，而其他情况下都必须大于这个size，所以我们就可以得到一个buckets，首先求出当前数字n属于buckets的那个桶当中，刷新这个桶的最小值和最大值，最后只需要关注相邻桶之间的上下限差别即可

---

Code

O(n)

class Solution:
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2 or min(nums) == max(nums):
            return 0
        
        mx, mi = max(nums), min(nums) # get the max and min value of the array
        size = (mx - mi) // (len(nums) - 1) or 1 # the minimum possibale gap, ceiling of the integer division
        buckets = [[None, None] for _ in range((mx - mi) // size + 1)] # set buckets
        
        for n in nums:
            bu = buckets[(n - mi) // size]
            bu[0] = n if bu[0] is None else min(n, bu[0])
            bu[1] = n if bu[1] is None else max(n, bu[1])
            
        buckets = [bu for bu in buckets if bu[0] is not None]
        return max([buckets[i][0] - buckets[i - 1][1] for i in range(1, len(buckets))])