What is the main approach to solve Maximum Gap efficiently?

Use bucket sort or radix sort to partition the array and compute the maximum difference between consecutive non-empty buckets.

Can I just sort the array normally for Maximum Gap?

Normal sorting works logically but does not meet the linear time requirement. Bucket or radix sort preserves O(n) time complexity.

How do I handle arrays with fewer than two elements?

Return 0, since there are no consecutive elements to form a gap, consistent with problem constraints.

Why is the maximum gap always between buckets, not inside a bucket?

Because each bucket holds a subrange, any gap within a bucket is smaller than the gap between buckets due to range partitioning.

Does GhostInterview provide hints specific to the array plus sorting pattern?

Yes, it focuses on identifying pattern matches and guiding toward bucket or radix sorting strategies for correct gap calculation.

#164

Medium

auto_awesome数组·排序

LeetCode 题解工作台

最大间距

给定一个无序的数组 nums ，返回数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0 。您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。示例 1: 输入: nums = [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9] ,…

数组排序桶排序基数排序

题目描述

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

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：桶排序

假设数组 $nums$ 有 $n$ 个元素，所有元素从小到大依次是 $nums_0$ 到 $nums_{n - 1}$ ，最大间距是 $maxGap$ 。考虑数组中的最大元素和最小元素之差。

nums_{n - 1} - nums_0 = \sum_{i = 1}^{n - 1} (nums_i - nums_{i - 1}) \le{maxGap} \times (n - 1)

因此 $maxGap \ge \dfrac{nums_{n - 1} - nums_0}{n - 1}$ ，即最大间距至少为 $\dfrac{nums_{n - 1} - nums_0}{n - 1}$ 。

可以利用桶排序的思想，设定桶的大小（即每个桶最多包含的不同元素个数）为 $\dfrac{nums_{n - 1} - nums_0}{n - 1}$ ，将元素按照元素值均匀分布到各个桶内，则同一个桶内的任意两个元素之差小于 ${maxGap}$ ，差为 ${maxGap}$ 的两个元素一定在两个不同的桶内。对于每个桶，维护桶内的最小值和最大值，初始时每个桶内的最小值和最大值分别是正无穷和负无穷，表示桶内没有元素。

遍历数组 ${nums}$ 中的所有元素。对于每个元素，根据该元素与最小元素之差以及桶的大小计算该元素应该分到的桶的编号，可以确保编号小的桶内的元素都小于编号大的桶内的元素，使用元素值更新元素所在的桶内的最小值和最大值。

遍历数组结束之后，每个非空的桶内的最小值和最大值都可以确定。按照桶的编号从小到大的顺序依次遍历每个桶，当前的桶的最小值和上一个非空的桶的最大值是排序后的相邻元素，计算两个相邻元素之差，并更新最大间距。遍历桶结束之后即可得到最大间距。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        mi, mx = min(nums), max(nums)
        bucket_size = max(1, (mx - mi) // (n - 1))
        bucket_count = (mx - mi) // bucket_size + 1
        buckets = [[inf, -inf] for _ in range(bucket_count)]
        for v in nums:
            i = (v - mi) // bucket_size
            buckets[i][0] = min(buckets[i][0], v)
            buckets[i][1] = max(buckets[i][1], v)
        ans = 0
        prev = inf
        for curmin, curmax in buckets:
            if curmin > curmax:
                continue
            ans = max(ans, curmin - prev)
            prev = curmax
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) using bucket or radix sort, as each element is placed in a bucket once and gaps are computed in a single pass. Space complexity is O(n) due to the buckets used to store min and max values across the array range.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion on linear time sorting alternatives like bucket sort or radix sort.
question_mark
Clarify how maximum gaps occur between buckets rather than within buckets.
question_mark
Check edge case handling for arrays with less than two elements or uniform values.

warning

常见陷阱

外企场景

error
Sorting the array normally violates the linear time constraint and may be penalized.
error
Failing to skip empty buckets can lead to incorrect maximum gap computation.
error
Not handling arrays with fewer than two elements results in invalid outputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum difference in a circularly sorted array using the same bucket principles.
arrow_right_alt
Compute the maximum gap when numbers can be negative or very large, requiring careful bucket range calculation.
arrow_right_alt
Apply a similar approach to floating-point arrays by scaling values into discrete buckets.

help

常见问题

外企场景

继续练习

#912 排序数组 #220 存在重复元素 III #347 前 K 个高频元素