给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。
假设答案法。N个数，根据最大值和最小值的范围等分成N+1个桶。每个桶只需要存当前桶的最大值和最小值。根据鸽笼原理，必然存在空桶。最后只需要遍历求【右桶min-左桶max】，返回最大值。最终答案可能来自相邻桶（这个很难想到），也可能来自跨桶（空桶的左侧和右侧就是跨桶），但是一定不会来自同一个桶内部的情况。另外，这道题是以空间复杂度换取时间复杂度
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{17, 13, 15, 0, 49, 47, 43, 99, 84}
ret := maxGap(arr)
fmt.Println(ret)
}
func maxGap(nums []int) int {
if len(nums) < 2 {
return 0
}
N := len(nums)
min := math.MaxInt64
max := math.MinInt64
for i := 0; i < N; i++ {
min = getMin(min, nums[i])
max = getMax(max, nums[i])
}
if min == max {
return 0
}
// 不止一种数，min~max一定有range, len个数据，准备len+1个桶
hasNum := make([]bool, N+1) // hasNum[i] i号桶是否进来过数字
maxs := make([]int, N+1) // maxs[i] i号桶收集的所有数字的最大值
mins := make([]int, N+1) // mins[i] i号桶收集的所有数字的最小值
bid := 0 // 桶号
for i := 0; i < N; i++ {
bid = bucket(nums[i], N, min, max)
mins[bid] = twoSelectOne(hasNum[bid], getMin(mins[bid], nums[i]), nums[i])
maxs[bid] = twoSelectOne(hasNum[bid], getMax(maxs[bid], nums[i]), nums[i])
hasNum[bid] = true
}
res := 0
lastMax := maxs[0] // 上一个非空桶的最大值
i := 1
for ; i <= N; i++ {
if hasNum[i] {
res = getMax(res, mins[i]-lastMax)
lastMax = maxs[i]
}
}
return res
}
// 如果当前的数是num，整个范围是min~max，分成了len + 1份
// 返回num该进第几号桶
func bucket(num int, N int, min int, max int) int {
return (num - min) * N / (max - min)
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
