Solution
from typing import List
from math import inf
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
mi, mx = min(nums), max(nums)
bucket_size = max(1, (mx - mi) // (n - 1))
bucket_count = (mx - mi) // bucket_size + 1
buckets = [[inf, -inf] for _ in range(bucket_count)]
for v in nums:
i = (v - mi) // bucket_size
buckets[i][0] = min(buckets[i][0], v)
buckets[i][1] = max(buckets[i][1], v)
ans = 0
prev = inf
for curmin, curmax in buckets:
if curmin > curmax:
continue
ans = max(ans, curmin - prev)
prev = curmax
return ans
if __name__ == "__main__":
sol = Solution()
print(sol.maximumGap([3,6,9,1]))
print(sol.maximumGap([10]))