francecil
commented
4 years ago 思路
利用桶排序和鸽巢原理 最大差值必然为桶间差值，而非桶内差值
/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function (nums) {
let min = Math.min(...nums)
let max = Math.max(...nums)
const bucketNum = nums.length
let buckets = []
const bucketSize = Math.floor((max - min) / bucketNum) + 1
// 计算每个桶的最大最小元素
for (let i = 0; i < nums.length; i++) {
const index = ~~((nums[i] - min) / bucketSize)
if (!buckets[index]) {
buckets[index] = {
maxVal: nums[i],
minVal: nums[i]
}
} else {
buckets[index].maxVal = Math.max(buckets[index].maxVal, nums[i])
buckets[index].minVal = Math.min(buckets[index].minVal, nums[i])
}
}
// 如果有多个元素放同个桶，必将有存在空桶
// 最大间隔绝对不是同个桶的元素间距离，而是不同桶间的距离
// 因此只需要记录前一个桶的最大元素与后一个桶的最小元素间的差值
let result = 0
let lastBucketIndex = -1
for (let i = 0; i < buckets.length; i++) {
if (buckets[i]) {
if (lastBucketIndex >= 0) {
result = Math.max(result, buckets[i].minVal - buckets[lastBucketIndex].maxVal)
//计算完后重置
lastBucketIndex = i
} else {
lastBucketIndex = i
}
}
}
return result
};
原题链接
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
示例 2:
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。