最大间距
难度:
标签:
题目描述
给定一个无序的数组 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)`而不是直接按照元素数量均分?
▷🦆
在初始化桶时,为何每个桶存储的是一个长度为2的数组,这两个元素分别代表什么?
▷🦆
如果数组中存在重复元素,这种方法处理重复元素时有什么特别的考虑吗?
▷