排序算法之：最小差值排序（MinDiff Sort）的进阶应用：优化相邻元素最大差值问题 题目描述 给定一个无序数组，要求在线性时间复杂度和线性空间复杂度内，找到排序后相邻元素之间的最大差值（即最大间隔）。例如，数组 [3, 6, 9, 1] 排序后为 [1, 3, 6, 9] ，相邻差值分别为 2、3、3，最大差值为 3。 解题思路 直接排序后遍历需 \(O(n \log n)\) 时间，但题目要求 \(O(n)\) 时间。此时可结合 桶排序 的思想，通过分桶策略避免全排序，仅关注桶间的最大间隔。 关键观察 最大差值一定不小于桶宽 ： 设数组长度为 \(n\)，最小值为 \(\min\)，最大值为 \(\max\)，则排序后最大差值 \( \geq \frac{\max - \min}{n-1} \)。 桶内差值无需计算 ： 将元素分配到 \(n\) 个桶中，每个桶宽 \( \text{bucketSize} = \frac{\max - \min}{n-1} \)。由于桶宽是平均差值，最大差值不可能出现在同一个桶内，只需比较相邻非空桶的边界差。 步骤详解 步骤 1：计算基本参数 遍历数组，找到最小值 \(\min\) 和最大值 \(\max\)。 若 \(\min = \max\)，说明所有元素相等，直接返回 0。 计算桶宽： \[ \text{bucketSize} = \frac{\max - \min}{n-1} \] 实际中需向上取整，但此处用浮点数即可，因为桶索引通过除法计算。 步骤 2：初始化桶 创建 \(n\) 个桶，每个桶只需记录桶内最小值和最大值（初始为空）。 桶索引计算公式： \[ \text{index} = \left\lfloor \frac{\text{num} - \min}{\text{bucketSize}} \right\rfloor \] 注意：最大值 \(\max\) 的索引为 \(n-1\)，需特殊处理（例如直接放入最后一个桶）。 步骤 3：分配元素到桶 遍历每个元素，根据索引放入对应桶： 若桶为空，将该元素同时设为桶的最小值和最大值。 否则更新桶的最小值或最大值。 步骤 4：计算最大间隔 遍历所有桶，记录前一个非空桶的最大值 \(\text{prevMax}\)。 遇到当前非空桶时，计算当前桶的最小值减去 \(\text{prevMax}\)，更新最大差值。 跳过空桶（因为最大间隔只与非空桶的边界相关）。 示例演示 以数组 [3, 6, 9, 1] 为例： \(\min = 1\)，\(\max = 9\)，\(n = 4\)，桶宽 \(\frac{9-1}{3} = 2.67\)。 分配桶： 桶 0：\([ 1, 3 ]\)（索引 0: \(\lfloor (1-1)/2.67 \rfloor=0\)，索引 1: \(\lfloor (3-1)/2.67 \rfloor=0\)） 桶 1：空 桶 2：\([ 6 ]\)（索引 \(\lfloor (6-1)/2.67 \rfloor=1.87 \rightarrow 1\)？需验证：实际应取整为 1，但 6 在桶 1？修正计算： 索引公式：\(\lfloor (值 - \min) / \text{bucketSize} \rfloor\) 值 6：\((6-1)/2.67 ≈ 1.87\)，向下取整为 1 → 桶 1 值 9：\((9-1)/2.67 ≈ 3.0\)，取整为 3，但桶索引最大为 \(n-1=3\)，故放入桶 3。 修正后桶分配： 桶 0: min=1, max=3 桶 1: min=6, max=6 桶 2: 空 桶 3: min=9, max=9 遍历非空桶： 桶 0 → 桶 1：差值 = \(6 - 3 = 3\) 桶 1 → 桶 3：差值 = \(9 - 6 = 3\) 最大差值为 3。 算法复杂度 时间复杂度：\(O(n)\)（遍历数组常数次）。 空间复杂度：\(O(n)\)（存储 \(n\) 个桶）。 边界情况处理 数组长度小于 2：直接返回 0。 所有元素相等：桶宽为 0，但通过 \(\min = \max\) 判断可提前返回 0。 浮点数精度：使用 double 计算桶宽，索引通过 floor 取整。 此方法通过桶排序思想优化了全排序的必要性，仅用线性时间即可找到最大间隔，是 最小差值排序（MinDiff Sort） 的典型进阶应用。