最大间距

记住这句：答案藏在「相邻非空桶之间」，桶内差值永远不够大。下面每一帧都在套它。

先定桶：最小 1、最大 9、共 5 个数，算出桶宽 size=2、桶数 5。每个桶只存它见过的最小值和最大值。

看第 0 个数 1（紫色）：用 (1-1)/2 算出它该进桶0。

1 落进桶0，这桶刚被点亮，min 和 max 都先记成 1。

看第 1 个数 3（紫色）：用 (3-1)/2 算出它该进桶1。

3 落进桶1，这桶刚被点亮，min 和 max 都先记成 3。

看第 2 个数 6（紫色）：用 (6-1)/2 算出它该进桶2。

6 落进桶2，这桶刚被点亮，min 和 max 都先记成 6。

看第 3 个数 9（紫色）：用 (9-1)/2 算出它该进桶4。

9 落进桶4，这桶刚被点亮，min 和 max 都先记成 9。

看第 4 个数 4（紫色）：用 (4-1)/2 算出它该进桶1。

4 也落进桶1，刷新这桶的 min=3、max=4。同桶内差值最多 1，不可能是答案。

所有数都入桶了。现在从左到右扫每个非空桶，只比「上一非空桶的 max」和「当前桶的 min」这一段距离。prev 起步用最小值 1。

轮到非空桶0（紫框）。跨桶间距 = 本桶最小 1 减去上一非空桶的 max 1，得 0。

0 没超过当前最大间距 0，ans 不变。prev 推进到本桶 max 1。

轮到非空桶1（紫框）。跨桶间距 = 本桶最小 3 减去上一非空桶的 max 1，得 2。

2 比之前的最大间距大，刷新 ans=2。再把 prev 推到本桶 max 4，准备比下一个非空桶。

轮到非空桶2（紫框）。跨桶间距 = 本桶最小 6 减去上一非空桶的 max 4，得 2。

2 没超过当前最大间距 2，ans 不变。prev 推进到本桶 max 6。

桶3 是空的（紫框）。空桶直接跳过，不参与比较，prev 保持 6。空桶的存在正说明这里有一道大缝隙。

轮到非空桶4（紫框）。跨桶间距 = 本桶最小 9 减去上一非空桶的 max 6，得 3。

3 比之前的最大间距大，刷新 ans=3。再把 prev 推到本桶 max 9，准备比下一个非空桶。

回头验证：把数排好是 [1, 3, 4, 6, 9]，相邻差里最大的正是 3。我们没真排序，只靠扫桶就 O(n) 得到了它。

边界先想清：单元素 0、全等 0、两元素即唯一差。

两个高频追问：与基数排序的取舍、桶数为何只和 n 相关。