leetcode
leetcode 151 ~ 200
最大间距

最大间距

难度:

标签:

题目描述

给定一个无序的数组 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 <= 105
  • 0 <= nums[i] <= 109

代码结果

运行时间: 122 ms, 内存: 33.6 MB


/*
思路:
1. 使用Java 8的Stream API进行排序。
2. 将数组转为流,排序后使用reduce方法计算最大差值。
3. 如果数组元素个数小于2,直接返回0。
*/
 
import java.util.Arrays;
import java.util.stream.IntStream;
 
public class MaximumGapStream {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int[] sorted = Arrays.stream(nums).sorted().toArray();
        return IntStream.range(1, sorted.length)
                .map(i -> sorted[i] - sorted[i - 1])
                .max()
                .orElse(0);
    }
}

解释

方法:

题解采用了桶排序的思路来解决问题。首先,如果数组长度小于2,直接返回0。计算数组最小值mn和最大值mx。接着计算桶的大小d,这是基于最大值和最小值的差以及数组长度来决定的,确保至少有一个元素在每个桶中。桶的数量计算基于(d + 1)来保证所有值都能放入桶中。每个桶用来存储该桶中的最小值和最大值。遍历数组,将每个元素放入相应的桶并更新该桶的最小值和最大值。最后,遍历所有桶,计算相邻非空桶之间的最大差值,即前一个桶的最大值和后一个桶的最小值之间的差。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算桶的大小时使用了公式`(mx - mn) // (n - 1)`而不是直接按照元素数量均分?
这个公式的目的是确保至少有一个元素在每个桶中,并且尽可能使相邻元素之间的间距最大化。公式`(mx - mn) // (n - 1)`计算的是理论上相邻元素的最大可能间距(如果元素均匀分布)。这样,我们可以通过保证每个桶至少包含一个元素(除了最大值和最小值之间可能的空桶),最大化相邻非空桶之间的差值,从而找到最大间距。如果直接按照元素数量均分,桶的数量会等于元素数量,这可能导致每个桶中只有一个元素,从而无法有效利用桶排序优化时间复杂度。
🦆
在初始化桶时,为何每个桶存储的是一个长度为2的数组,这两个元素分别代表什么?
在初始化桶时,每个桶中存储的两个元素分别代表该桶中的最小值和最大值。这是因为最终计算最大间距时,我们关心的是相邻非空桶之间的最大差值,这个差值是由前一个桶的最大值和后一个桶的最小值之间的差计算得来的。因此,为了方便计算这种差值,我们在每个桶中维护一个最小值和一个最大值。
🦆
如果数组中存在重复元素,这种方法处理重复元素时有什么特别的考虑吗?
这种方法在处理重复元素时没有特别的考虑或需求。重复元素会被放入同一个桶中,因为它们的值相同。在桶内部,即使存在多个相同的元素,我们仍然更新桶中的最小值和最大值,但对于重复值,这不会改变桶的最小值或最大值。因此,重复元素不影响最终计算相邻非空桶之间的最大差值。桶排序的逻辑保证了即使存在重复元素,也能正确计算出最大间距。

相关问题