164. Maximum Gap

下面这个解法，不仅错误地使用了 局部变量，还超时了。

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
#         n = len(nums)
#         if n < 2: return 0

#         nums = sorted(nums)
#         res = nums[1] - nums[0]
#         for i in range(n - 1):
#             if nums[i + 1] - nums[i] > res:
#                 res = nums[i + 1] - nums[i]

#         return res
        '''
        I think dictionary is fine in this work.
        When I search one element, I check the one great and less than it.
        '''

        '''
        the second thought is use an array
        '''
        n = len(nums)
        if n < 2: return 0
        imax = nums[0]
        imin = nums[0]
        for n in nums:
            if n > imax:
                imax = n
            if n < imin:
                imin = n
        arr = []
        for i in range(imin, imax + 1):
            arr.append(-1)
        for n in nums:
            arr[n - imin] = 1
        nums = [i + imin for i, n in enumerate(arr) if n == 1]

        res = 0
        # i not initialed?
        i = 1
        for i in range(1, n):
            if nums[i] - nums[i - 1] > res:
                res = nums[i] - nums[i - 1]
        return res

又错误地使用了局部变量，我觉得有必要仔细学习一下 Python 的闭包的概念了。

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
#         n = len(nums)
#         if n < 2: return 0

#         nums = sorted(nums)
#         res = nums[1] - nums[0]
#         for i in range(n - 1):
#             if nums[i + 1] - nums[i] > res:
#                 res = nums[i + 1] - nums[i]

#         return res
        '''
        I think dictionary is fine in this work.
        When I search one element, I check the one great and less than it.
        '''

        '''
        the second thought is use an array
        '''
#         n = len(nums)
#         if n < 2: return 0
#         imax = nums[0]
#         imin = nums[0]
#         for n in nums:
#             if n > imax:
#                 imax = n
#             if n < imin:
#                 imin = n
#         arr = []
#         for i in range(imin, imax + 1):
#             arr.append(-1)
#         for n in nums:
#             arr[n - imin] = 1
#         nums = [i + imin for i, n in enumerate(arr) if n == 1]

#         res = 0
#         # i not initialed?
#         i = 1
#         n = len(nums)
#         for i in range(1, n):
#             if nums[i] - nums[i - 1] > res:
#                 res = nums[i] - nums[i - 1]
#         return res
        '''
        bucket
        '''
        n = len(nums)
        if n < 2: return 0

        bmax = [-1 for _ in range(n - 1)]
        bmin = [-1 for _ in range(n - 1)]

        imax = nums[0]
        imin = nums[0]
        for i in range(1, n):
            imax = max(imax, nums[i])
            imin = max(imin, nums[i])
        if imax == imin: return 0
        step = float(imax - imin) / float(n - 1)
        # what if 2 2 2 2 2 2 1000?
        # if step is 0: return 0
        # in this case, if imax == imin, then return 0

        for n in nums:
            bidx = int(float(n - imin) / step)
            if bmax[bidx] == -1:
                bmax[bidx] = n
            else:
                bmax[bidx] = max(bmax[bidx], n)

            if bmin[bidx] == -1:
                bmin[bidx] = n
            else:
                bmin[bidx] = min(bmin[bidx], n)

        for i in range(1, n - 1):
            if bmax[n - 2 - i] == -1:
                bmax[n - 2 - i] = bmax[n - 1 - i]
            if bmin[i] == -1:
                bmin[i] == bmin[i - 1]
        res = 0

        for i in range(1, n - 1):
            res = max(bmin[i] - bmax[i - 1], res)

        return res

这个代码的主要错误有五个：

1. bmax/bmin 的桶的个数有 n 个，不是 n - 1 个

2. 在 for n in nums: 之后，n 就改变了

3. 在求 imax/imin 的时候，使用了两个 max

4. res = max(bmin[i] - bmax[i], res)

5. bmin[i] == bmin[i - 1]