问题描述

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

问题分析

AC代码

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n < 2:
            return 0
        b = a = nums[0]
        for i in nums:
            if i > b:
                b = i
            if i < a:
                a = i
        if a == b:
            return 0
        size = (b-a) / (n-1)
        if (b-a) % (n-1) != 0:
            size += 1
        num = (b-a) / size + 1
        bucket_b = [None for i in range(num)]
        bucket_a = [None for i in range(num)]
        for i in nums:
            bucket = (i-a)/size
            if not bucket_b[bucket] or i > bucket_b[bucket]:
                bucket_b[bucket] = i
            if not bucket_a[bucket] or i < bucket_a[bucket]:
                bucket_a[bucket] = i
        gap = 0
        p = 0
        while True:
            q = p+1
            while q < num and not bucket_a[q]:
                q += 1
            if q == num:
                break
            if gap < bucket_a[q] - bucket_b[p]:
                gap = bucket_a[q] - bucket_b[p]
            p = q

        return gap

Runtime: 59 ms, which beats 83.05% of Python submissions.