LeetCode刷题实战164：最大间距-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大间距 ，我们先来看题面：

https://leetcode-cn.com/problems/maximum-gap/

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

题意

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

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

样例

示例 1:

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

示例 2:

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

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

解题

https://www.cnblogs.com/powercai/p/11299825.html

思路:

不用线性时间复杂度，其实就是排序的题！代码如下：

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2: return 0
        res = 0
        nums.sort()
        for i in range(1, n):
            res = max(res, nums[i] - nums[i - 1])
        return res

下面介绍一下用桶排序的方法：

首先，要知道很关键一点：相邻的最大差值一定不小于该数组的最大值减去最小值除以间隔个数，取上界。即

⌈ m a x n u m - m i n n u m (n - 1) ⌉ " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> ⌈ m a x n u m - m i n n u m (n - 1) ⌉ ⌈ m a x n u m - m i n n u m (n - 1) ⌉

，这里的 n 是数组的个数。

我们可以用反证法证明，如果小于，会怎么呢？比如 [1, 2, 5], 利用上式得

g a p = 5 - 1 2 = 2 " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> g a p = 5 - 1 2 = 2 g a p = 5 - 1 2 = 2

。如果假设相邻间隔最大为 1，那必然不能组成以上数组！

接下来，我们开始放桶，一个桶里放多少个数呢？我们可以把相邻间隔小于 gap放在一个桶里，那么最大间隔一定在相互桶之间产生！

如何判断这个数在哪个桶里呢？我们用

⌊ n u m - m i n n u m g a p ⌋ " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> ⌊ n u m - m i n n u m g a p ⌋ ⌊ n u m - m i n n u m g a p ⌋

表示 num 在哪个桶里（换句话说，离min_num有几个gap）。我们比如数组为 [1, 2, 3, 4，7],我们排除最大值和最小值，把其他数组放入桶中，如下图：

|     |      |      |
|2，3 |      | 4    |       
|_ _ _|      | _ _ _|

同一个桶里，绝对不会出现最大的相邻的差值！

所以，我们只需要比较桶之间的差值，这样我们只需要保持同一桶里的最大值，和最小值即可！

代码如下：

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2: return 0
        max_num = max(nums)
        min_num = min(nums)
        gap = math.ceil((max_num - min_num)/(n - 1))
        bucket = [[float("inf"), float("-inf")] for _ in range(n - 1)]
        #print(bucket)
        # 求出每个桶的最大值，和最小值
        for num in nums:
            if num == max_num or num == min_num:
                continue
            loc = (num - min_num) // gap
            bucket[loc][0] = min(num, bucket[loc][0])
            bucket[loc][1] = max(num, bucket[loc][1])
        ##print(bucket)
        # 遍历整个桶
        preMin = min_num
        res = float("-inf")
        for x, y in bucket:
            if x == float("inf") :
                continue
            res = max(res, x - preMin)
            preMin = y
        res = max(res, max_num - preMin)
        return res

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode1-160题汇总，希望对你有点帮助！

LeetCode刷题实战161：相隔为1的编辑距离

LeetCode刷题实战162：寻找峰值

LeetCode刷题实战163：缺失的区间

​LeetCode刷题实战164：最大间距

题意

解题

思路:

LeetCode刷题实战164：最大间距