maxGap

# -*- coding: utf-8 -*- 
import random
def GenerateRandomList(number, size):
	temp = []
	random_legth = random.randint(0, size)
	current_length = 0
	while current_length < random_legth:
		temp.append(random.randint(1, number))
		current_length += 1
	return temp
    
def maxGap(arr):
    length= len(arr)
    if arr is None or length < 2:
        return 0
    max_val = max(arr)
    min_val = min(arr)
    max_list = [min_val for _ in range(length + 1)]
    min_list = [max_val for _ in range(length + 1)]
    hasNumber = [False for _ in range(length + 1)]
    print(hasNumber)
    for i in range(length):
        index = which_bucket(arr[i], length, min_val, max_val)
        hasNumber[index] = True
        min_list[index] = min(arr[i], min_list[index])
        max_list[index] = max(arr[i], max_list[index])
    
    res = set()   
    i = 0
    while i < length:
        if hasNumber[i]:
            j = i + 1
            while not hasNumber[j]:
                j += 1
            res.add(min_list[j] - max_list[i])
        i += 1
    return max(res)

# length 为数组的长度
def which_bucket(num, length, min_val, max_val):
    return (num - min_val) * length // (max_val - min_val)


l = [3, 2, 1, 6, 7, 12]

ans = maxGap(l)

print(ans)