package main

func maximumGap(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	min, max := nums[0], nums[0]
	for i := 1; i < n; i++ {
		if nums[i] < min {
			min = nums[i]
		}
		if nums[i] > max {
			max = nums[i]
		}
	}
	minMaxGap := (max - min) / (n - 1)
	if minMaxGap == 0 {
		minMaxGap++
	}
	bucketNum := (max-min)/minMaxGap + 1 // Bucket sort, divide the whole area into buckets
	bucketMin := make([]int, bucketNum)
	bucketMax := make([]int, bucketNum)
	used := make([]bool, bucketNum)
	for i := 0; i < n; i++ {
		idx := (nums[i] - min) / minMaxGap
		if !used[idx] {
			bucketMin[idx] = nums[i]
			bucketMax[idx] = nums[i]
			used[idx] = true
			continue
		}
		if nums[i] < bucketMin[idx] {
			bucketMin[idx] = nums[i]
		}
		if nums[i] > bucketMax[idx] {
			bucketMax[idx] = nums[i]
		}
	}
	prevBucketMax, maxGap := min, 0
	for i := 0; i < bucketNum; i++ {
		if used[i] {
			if bucketMin[i]-prevBucketMax > maxGap {
				maxGap = bucketMin[i] - prevBucketMax
			}
			prevBucketMax = bucketMax[i]
		}
	}
	return maxGap
}

// func main() {
// 	println(maximumGap([]int{3, 6, 9, 1}), 3)
// 	println(maximumGap([]int{1, 1, 1, 1}), 0)
// 	println(maximumGap([]int{100, 3, 2, 1}), 97)
// 	println(maximumGap([]int{10}), 0)
// }