[数据结构与算法]python 相邻两数的最大差值

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N),且要求不能用非基于比较的排序。
思路利用桶的特性

代码如下：

class Solution:
    def maxGap(self, arr):
        if not arr or len(arr) < 2:
            return 0
        length = len(arr)
        min_val = float("inf") # 无穷大
        max_val = float("-inf") # 无穷小
        for i in arr:
            min_val = min(min_val, i)
            max_val = max(max_val, i)
        if min_val == max_val:  # 数组中只有一种数
            return 0
        has_num = [False] * (length + 1)
        maxs = [0] * (length + 1)
        mins = [0] * (length + 1)
        min_val = int(min_val)
        max_val = int(max_val)
        for i in range(length):
            bid = self.bucket(arr[i], length, min_val, max_val)
            mins[bid] = min(mins[bid], arr[i]) if has_num[bid] else arr[i]
            maxs[bid] = max(maxs[bid], arr[i]) if has_num[bid] else arr[i]
            has_num[bid] = True
        res = 0
        lastMax = maxs[0]
        for i in range(1, length+1):
            if has_num[i]:
                res = max(res, mins[i] - lastMax)  # 后一桶的最大值减去前一个桶的最小值
                lastMax = maxs[i]
        return res

    def bucket(self, num, length, min, max):
        """进那只桶"""
        return int((num - min) * length / (max - min))

if __name__ == '__main__':
    s = Solution()
    arr = [10, 20, 34, 19, 50, 20]
    print(s.maxGap(arr))