友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
164. 最大间距
给定一个无序的数组 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
思路分析
使用比特位表示每个数字！这样统计每个比特位之间的差值即可。
使用比特位并不是最优解，内存消耗可能比较大。看题解，应该使用基数排序。抽空学习一下！
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-29 11:13:03
*/
public int maximumGap(int[] nums) {
int max = Arrays.stream(nums).max().orElse(0);
long[] bits = new long[max / 64 + 1];
for (int num : nums) {
int index = num / 64;
int step = num % 64;
bits[index] = bits[index] | (1L << step);
}
int result = 0;
int pre = -1;
for (int i = 0; i < bits.length; i++) {
long bit = bits[i];
if (bit == 0) {
continue;
}
int step = 0;
int start = i * 64;
while (bit != 0) {
if ((bit & 1) == 1) {
if (pre == -1) {
pre = start + step;
} else {
int next = start + step;
result = Math.max(result, next - pre);
pre = next;
}
}
step++;
// 注意：这里要使用 >>> 无符号右移
bit >>>= 1;
}
}
return result;
}
// // 最简单的写法
// public int maximumGap(int[] nums) {
// Arrays.sort(nums);
// int result = 0;
// for (int i = 1; i < nums.length; i++) {
// result = Math.max(result, nums[i] - nums[i - 1]);
// }
// return result;
// }