无序数组计算排序后最大相邻差

如题目所示，给定数组[2,6,3,4,5,10,9]，排序后的最大相邻差为9-6=3。想必你想到的方法是先运用冒泡或者快速排序，先将数组进行排序，然后循环求出来最大相邻差。这个时间复杂度为nlogn。
我们可以使用桶排序的方式计算最大相邻差，其中这个最大相邻差为右桶的最小值减去左桶的最大值。
桶的个数为数组的个数，桶的取值步长为(maxvalue-minvalue)/(len(array)-1)
形如

最大距离差为9min-6max=3

python 代码如下

class Bucket():
    def __init__(self) -> None:
        self.min = None
        self.max = None


def get_max_dinstinct(array: list = []):
    max_value = array[0]
    min_value = array[0]
    for i in range(0,len(array)):
        if array[i]>max_value:
            max_value=array[i]
        if array[i]<min_value:
            min_value=array[i]
            
    d = max_value-min_value
    if d==0:
        return 0
    # 初始化桶
    bucket_num = len(array)
    buckets = []
    for i in range(bucket_num):
        buckets.append(Bucket())
        
    # 遍历原始数组，确定每个桶的最大最小值
    for i in range(0,len(array)):
        # 确定数组元素所属的桶下表
        index = int((array[i]-min_value)*(bucket_num-1)/d)
        if buckets[index].min is None or array[i]<buckets[index].min:
            buckets[index].min = array[i]
        if buckets[index].max is None or array[i]>buckets[index].max:
            buckets[index].max = array[i]
    # 遍历桶计算最大距离
    left_max = buckets[0].max
    max_distinct = 0
    
    for _,value in enumerate(buckets):
        if value.min is None:
            continue
        if value.min-left_max>max_distinct:
            max_distinct = value.min-left_max
        left_max = value.max
        
    return max_distinct


print(get_max_dinstinct([2,6,5,4,3,10,9]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47