题目解析：
- 准备桶，一个数组有N个数，则准备N+1个桶。
- 遍历整个数组，找到最小值和最大值。（如果相等，最大差值为0，直接返回。如果不等，最小值放在第0号桶，最大值放在第N号桶，剩下的等分）
- 相邻两数可能来自相邻、或跨桶。
- 设置空桶的目的: 否定最大差值一定不来自相同桶。
package main
import "fmt"
func Min(x, y int) int {
if x < y {
return x
}
return y
}
func Max(x, y int) int {
if x > y {
return x
}
return y
}
func bucket(num int, len int, min int, max int) int {
return ((num - min) * len / (max - min))
}
func maxGap(nums []int) int {
min := int(^uint(0) >> 1)
max := 0
for i := range nums {
min = Min(min, nums[i])
max = Max(max, nums[i])
}
if min == max {
return 0
}
len := len(nums)
hasNum := make([]bool, len+1)
maxs := make([]int, len+1)
mins := make([]int, len+1)
for i := 0; i < len; i++ {
bid := bucket(nums[i], len, min, max)
if hasNum[bid] {
mins[bid] = Min(mins[bid], nums[i])
maxs[bid] = Max(maxs[bid], nums[i])
} else {
mins[bid] = nums[i]
maxs[bid] = nums[i]
}
hasNum[bid] = true
}
res := 0
lastMax := maxs[0]
for i := 1; i <= len; i++ {
if hasNum[i] {
res = Max(res, mins[i]-lastMax)
lastMax = maxs[i]
}
}
return res
}
func main() {
nums := []int{1, 19, 9, 4}
ret := maxGap(nums)
fmt.Println(ret)
}
