给定一个无序的数组 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^5
- 0 <= nums[i] <= 10^9
解题：
func maximumGap(nums []int) int {
sort.Ints(nums)
r := 0
for i := 1; i < len(nums); i++ {
if nums[i]-nums[i-1] > r {
r = nums[i] - nums[i-1]
}
}
return r
}官方解答：
1.基数排序
func maximumGap(nums []int) (ans int) {
n := len(nums)
if n < 2 {
return
}
buf := make([]int, n)
maxVal := max(nums...)
for exp := 1; exp <= maxVal; exp *= 10 {
cnt := [10]int{}
for _, v := range nums {
digit := v / exp % 10
cnt[digit]++
}
for i := 1; i < 10; i++ {
cnt[i] += cnt[i-1]
}
for i := n - 1; i >= 0; i-- {
digit := nums[i] / exp % 10
buf[cnt[digit]-1] = nums[i]
cnt[digit]--
}
copy(nums, buf)
}
for i := 1; i < n; i++ {
ans = max(ans, nums[i]-nums[i-1])
}
return
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}2.基于桶的算法
type pair struct{ min, max int }
func maximumGap(nums []int) (ans int) {
n := len(nums)
if n < 2 {
return
}
minVal := min(nums...)
maxVal := max(nums...)
d := max(1, (maxVal-minVal)/(n-1))
bucketSize := (maxVal-minVal)/d + 1
// 存储 (桶内最小值，桶内最大值) 对，(-1, -1) 表示该桶是空的
buckets := make([]pair, bucketSize)
for i := range buckets {
buckets[i] = pair{-1, -1}
}
for _, v := range nums {
bid := (v - minVal) / d
if buckets[bid].min == -1 {
buckets[bid].min = v
buckets[bid].max = v
} else {
buckets[bid].min = min(buckets[bid].min, v)
buckets[bid].max = max(buckets[bid].max, v)
}
}
prev := -1
for i, b := range buckets {
if b.min == -1 {
continue
}
if prev != -1 {
ans = max(ans, b.min-buckets[prev].max)
}
prev = i
}
return
}
func min(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v < res {
res = v
}
}
return res
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}