左边和右边的最大差值

2019-01-05

1 无序

一个无序数组，找到左边的一个数和右边的一个数的最大差值

if __name__ == '__main__':
    nums = [5, 11, 3, 10, 6, 1, 8, 4, 3, 2]
    maxdiff = 0
    minnum = nums[-1]
    for i in range(len(nums)-2, -1, -1):
        if nums[i] < minnum:
            minnum = nums[i]
        else:
            maxdiff = max(maxdiff, nums[i] - minnum)
    print(maxdiff)

2 有序

164. 最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。

桶排序、计数排序和基数排序的时间复杂度和空间复杂度都是线性的。

试着用了桶排序、计数排序和基数排序都因为内存溢出没有运行通过。然后用了python自带的排序就通过了。

class Solution:
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0
        if len(nums) == 2:
            return abs(nums[0] - nums[1])
        nums.sort()
        maxdiff = 0
        for i in range(len(nums)-1):
            maxdiff = max(maxdiff, nums[i+1] - nums[i])
        return maxdiff