题解 | 数组排序之后相邻数的最大差值

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}

		arr := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		fmt.Println(process(arr))
	}
}

type Bucket struct {
	minnu  int
	maxnu  int
	isused bool
}

func process(arr []int) int {
	if len(arr) < 2 {
		return 0
	}

	minnu, maxnu := arr[0], arr[0]
	for i := 1; i < len(arr); i++ {
		minnu = min(minnu, arr[i])
		maxnu = max(maxnu, arr[i])
	}

	// 保证interfal不为0
	interfal := (maxnu-minnu)/(len(arr)+1) + 1
	// 至少有一个空桶，
	bucket := make([]Bucket, len(arr)+1)

	for _, v := range arr {
		index := (v - minnu) / interfal
		if !bucket[index].isused {
			bucket[index].isused = true
			bucket[index].minnu = v
			bucket[index].maxnu = v
		} else {
			bucket[index].minnu = min(bucket[index].minnu, v)
			bucket[index].maxnu = max(bucket[index].maxnu, v)
		}
	}

	first := true
	premax := 0
	maxres := 0
	for _, v := range bucket {
		if v.isused && first {
			premax = v.maxnu
			first = false
		} else if v.isused {
			maxres = max(v.minnu-premax, maxres)
			premax = v.maxnu
		}
	}
	return maxres
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}