题目描述

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

示例

示例 1：

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例2：

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

说明：

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

解答方法

方法一：桶排序

思路

https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode/

代码

import math
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        
        max_val = max(nums)
        min_val = min(nums)
        if max_val == min_val:
            return 0
        #桶的大小以及数量
        bucket_size = math.ceil((max_val - min_val) / (len(nums) - 1)) 
        print(bucket_size)
        bucket_num = (max_val - min_val) // bucket_size + 1
        bucket = [[float('inf'),float('-inf'),False] for _ in range(bucket_num)]
        #依次把nums中每个元素添加到对应的桶中，并存储最大值最小值
        for num in nums:
            index = (num - min_val) // bucket_size
            bucket[index][2] = True
            bucket[index][0] = min(bucket[index][0], num)
            bucket[index][1] = max(bucket[index][1], num)
        #遍历每个桶
        res = 0
        pre_max = bucket[0][1]
        for n in range(1,len(bucket)):
            if not bucket[n][2]:
                continue
            res = max(res, bucket[n][0] - pre_max)
            pre_max = bucket[n][1]
        return res

时间复杂度

空间复杂度