mirror of https://github.com/doocs/leetcode.git
22 lines
710 B
Python
22 lines
710 B
Python
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
|