原文链接: https://leetcode-cn.com/problems/maximum-gap

英文原文

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

 

Example 1:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

中文题目

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

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

示例 2:

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

说明:

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

通过代码

高赞题解

前言：这道题的难点在于如何用线性的时空复杂度来解决。直接sort然后遍历数组当然可以解决问题，但是面试的时候这种解法肯定是不能让面试官满意的。

正文

桶排序的两个核心问题：

1. 每个桶的长度是多少？换句话说，每个桶放置元素的范围是什么？
2. 一共要准备多少个桶？

分析和解答：

1. 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。

$$每个桶的长度 = \max(1,\lfloor{{\max(nums) - \min(nums)} \over {len(nums) - 1}}\rfloor)\tag{1}$$ 

2. 确定桶的数量，最后的加一保证了数组的最大值也能分到一个桶。
$$桶的数量 = \lfloor{{\max(nums) - \min(nums)} \over {每个桶的长度}}\rfloor + 1\tag{2}$$



3. 我们的做法是要将数组中的数放到一个个桶里面，不断更新更大的（后一个桶内元素的最小值 - 前一个桶内元素的最大值），最后就得到了答案。

4. 如何确定每个数应该对应哪个桶？
$$location = {{nums[i] - \min(nums)} \over {每个桶的长度}}\tag3$$

举个栗子

nums = [1,3,4,5,6,10,11,12,17]
每个桶的长度 = （17 - 1） / (9-1) = 2
桶的个数 = （17-1）/ 2 + 1 = 9
所以我们的桶为（左闭右开）：
| 区间 | [1,3) | [3,5) | [5,7) | [7,9) | [9,11) | [11,13) | [13,15) | [15,17) | [17,19) |
|——|——-|——-|——-|——-|——–|———|———|———|———|
| 元素 | 1 | 3,4 | 5,6 | | 10 | 11,12 | | | 17 |

差值	3-1 = 2	5-4 = 1	10-6 = 4	11-10 = 1	17-12 = 5
答案 = max（差值） = 5

更新

就大家在评论区的讨论做一些说明：

1. 有同学提到可以将（1）式代入到（2）中从而化简得到桶的数量就是数组长度的这一结论，这里是不可以代入化简的，因为我们在这里进行了取整操作。上面的两个公式也相应更新成更严谨的数学表达。
2. 在桶长度这里我们进行了和1取max的操作，这是为了一些边界条件的情况，比如数组是[1,1,1,1]。当然我们也可以不取max，把向下取整改为向上取整。
3. 对第一点补充：如果我们把上面栗子的最后一个数改成16，那么每个桶的长度就是1，桶的个数就变成了16，于是出现了7个空桶。
4. 在所有排序算法里，我们一般认为快速排序是速度相对较快的，然而桶排序在大多数情况下比快速排序还要快，但是它付出的代价就是牺牲$O(n)$空间的复杂度，且比归并排序的空间占用要多一点点，多出来的一点点就是可能出现的空桶。

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        
        # 一些初始化
        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0
        
        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]
        
        # 把数字放入桶中
        for i in range(len(nums)):
            loc = (nums[i] - min_) // each_bucket_len
            buckets[loc].append(nums[i])
        
        # 遍历桶更新答案
        prev_max = float('inf')
        for i in range(len(buckets)):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i])-prev_max)
            
            if buckets[i]:
                prev_max = max(buckets[i])
                
        return max_gap

统计信息

通过次数	提交次数	AC比率
61672	101272	60.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言