相邻数最大差值

今天群里有人问了一道面试题，题目是N个未排序的整数，在线性时间内，求N个整数在数轴上相邻两个数之间的最大差值。

首先我想吐槽（莫怪~）群里某同学给出的一个解法，用桶排序+线性扫描，按照那位同学的意思，桶排序是O(n)，所以整个过程是O(n)。然而并没有什么卵用，这位同学可能不是很了解桶排序的脾气，因为桶排序最乐观情况下才是O(n)，而这道题如果使用排序，那结果应该是O(nlogn)。

然后我给出了我的解题思路：

1. 求 N 个数最大值 MAX，最小值 MIN
2. 把 [MIN, MAX) 之间平均分成 N 桶，并且补一个桶 [MAX, MAX + AVG)，把所有数字放到对应桶里，并且求出每个桶最大值 BMIN 最小值 BMAX
3. MAX_INTERVAL=MAX(MAX_INTERVAL, 非空桶.BMIN - 前一个非空桶.BMAX)

观点如下：

1. 如果桶内有多个数，桶内任意数间差值必然小于平均值
2. 如果两非空桶之间存在空桶，当前非空桶BMIN的值 - 前一个非空桶.BMAX >=平均值
3. 有N+1个桶，不存在每个桶正好分到一个，必然存在至少一个空桶

最后Talk is cheap, but no comment

func maxDiff(A []int) int {
	N := len(A)
	min := A[0]
	max := A[0]
	for i := 0; i < N; i++ {
		if A[i] > max {
			max = A[i]
		}
		if A[i] < min {
			min = A[i]
		}
	}
	avg := float32(max-min) / float32(N)
	B := make([]struct {
		used bool
		bmax int
		bmin int
	}, N+1)
	for i := 0; i < N; i++ {
		b := &B[int(float32(A[i]-min)/avg)]
		if b.used {
			if A[i] > b.bmax {
				b.bmax = A[i]
			} else if A[i] < b.bmin {
				b.bmin = A[i]
			}
		} else {
			b.bmax = A[i]
			b.bmin = A[i]
			b.used = true
		}
	}
	diff := 0
	lb := 0
	for i := 1; i <= N; i++ {
		if !B[i].used {
			continue
		}
		if B[i].bmin-B[lb].bmax > diff {
			diff = B[i].bmin - B[lb].bmax
		}
		lb = i
	}
	return diff
}