164.md

164. Maximum Gap

Solution 1 (time O(n), space(O(n))

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n < 2:
            return 0
        max_val = max(nums)
        exp = 1
        temp = [0] * n
        while max_val >= exp:
            cnt = [0] * 10
            for num in nums:
                digit = (num // exp) % 10
                cnt[digit] += 1
            for i in range(1, 10):
                cnt[i] += cnt[i - 1]
            for num in nums[::-1]:
                digit = (num // exp) % 10
                temp[cnt[digit] - 1] = num
                cnt[digit] -= 1
            nums = temp[:]
            exp = exp * 10
        ans = -float("inf")
        for i in range(1, n):
            ans = max(ans, nums[i] - nums[i - 1])
        return ans