Участник:Evgin/maximum gap py

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/maximum-gap/

Python3

Навеяно bucket sort-ом

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        min_, max_ = min(nums), max(nums)
        delta = max_ - min_
        if delta == 0:
            return 0
        size = int(delta / (len(nums) - 1)) or 1
        buckets = [[None, None] for _ in range(int(delta / size) + 1)]
        for num in nums:
            bucket = buckets[ int((num - min_) / size) ]
            bucket[0] = num if bucket[0] is None else min(bucket[0], num)
            bucket[1] = num if bucket[1] is None else max(bucket[1], num)
        buckets = [bucket for bucket in buckets if bucket[0] is not None]
        return max(buckets[i][0] - buckets[i - 1][1] for i in range(1, len(buckets)))