maximum_gap.go

package maximum_gap

funcmaximumGap(nums []int) int {
iflen(nums) <2 {
return0
 }
max, min:=nums[0], nums[0]
fori:=1; i<len(nums); i++ {
ifnums[i] >max {
max=nums[i]
 }
ifnums[i] <min {
min=nums[i]
 }
 }
bucketSize:= (max-min)/len(nums) +1
bucket:=make([][]int, len(nums))
fori:=rangenums {
idx:= (nums[i] -min) /bucketSize
iflen(bucket[idx]) ==0 {
bucket[idx] = []int{nums[i], nums[i]}
 } else {
ifnums[i] <bucket[idx][0] {
bucket[idx][0] =nums[i]
 }
ifnums[i] >bucket[idx][1] {
bucket[idx][1] =nums[i]
 }
 }
 }
ret:=bucket[0][1] -bucket[0][0]
pre:=0
fori:=1; i<len(nums); i++ {
iflen(bucket[i]) ==0 {
continue
 }
ifbucket[i][0]-bucket[pre][1] >ret {
ret=bucket[i][0] -bucket[pre][1]
 }
pre=i
 }
returnret
}