排序算法之：基于“最小差值排序”（MinDiff Sort）的进阶应用：优化相邻元素最大差值问题的动态规划解法（二次讲解） 题目描述 给定一个无序整数数组 nums ，其长度为 n ，你需要先对数组排序，然后计算排序后相邻元素之间的差值。目标是找到 最大差值 ，但要求算法的时间复杂度为 O(n)，空间复杂度为 O(n)。 这是一个经典问题，通常称为“最大间距”（Maximum Gap）。直接排序后扫描需要 O(n log n) 时间，但通过“桶排序+动态规划”思想可以在 O(n) 时间内解决。本题将深入讲解如何通过“最小差值排序”的变体实现优化。 解题过程循序渐进讲解 步骤1：问题转化 设数组最小值为 min_val ，最大值为 max_val ，元素个数为 n 。 如果 n < 2 ，最大差值为 0。 排序后相邻元素的最大差值至少为 ceil((max_val - min_val) / (n-1)) （将区间均匀分成 n-1 段时的平均间距）。 步骤2：桶的设计 创建 n-1 个桶，每个桶负责一个区间范围。 区间长度（桶宽）为 bucket_size = ceil((max_val - min_val) / (n-1)) 。 第 i 个桶覆盖的数值区间为： [min_val + i * bucket_size, min_val + (i+1) * bucket_size) ，最后一个桶包含右端点。 步骤3：元素放入桶中 遍历数组，将每个元素 num 放入对应的桶： bucket_id = (num - min_val) / bucket_size （整数除法）。 每个桶只需要记录桶内元素的最小值和最大值（因为桶内最大差值不会超过 bucket_size-1 ，而最大差值一定出现在相邻桶之间）。 步骤4：动态规划（扫描桶） 按桶编号从小到大扫描，维护 前一个非空桶的最大值 （记为 prev_max ）。 对当前非空桶，其最小值为 curr_min ，则当前可能的最大差值为 curr_min - prev_max 。 更新最大差值，并将 prev_max 设为当前桶的最大值。 初始时， prev_max 设为第一个桶的最大值（因为第一个桶一定包含 min_val ）。 步骤5：正确性证明 由于桶宽为平均间距，最大差值一定不小于桶宽，因此最大差值 不可能出现在同一个桶内部 ，只可能出现在相邻桶之间（或间隔空桶的桶之间）。 通过记录每个桶的 min 和 max，并比较相邻非空桶的（当前桶 min - 前一个非空桶 max），即可覆盖所有可能的最大差值情况。 步骤6：复杂度分析 时间复杂度：O(n)，一次遍历求最大最小值，一次遍历放入桶，一次遍历扫描桶。 空间复杂度：O(n)，存储 n-1 个桶的信息。 示例 输入： nums = [3, 6, 9, 1] min_val=1, max_val=9, n=4 bucket_size = ceil((9-1)/(4-1)) = ceil(8/3) = 3 桶区间： 桶0: [ 1, 4) 桶1: [ 4, 7) 桶2: [ 7, 10 ] 放元素： 3 → 桶0 (min=3, max=3) 6 → 桶1 (min=6, max=6) 9 → 桶2 (min=9, max=9) 1 → 桶0 (min=1, max=3) 扫描桶： 桶0: min=1, max=3, prev_ max=3 桶1: min=6, max=6, 差值=6-3=3 桶2: min=9, max=9, 差值=9-6=3 最大差值 = 3。 关键点总结 利用“最大差值不小于平均间距”的性质，将元素分布到桶中，确保最大差值不会出现在桶内。 只需记录每个桶的 min 和 max，忽略桶内具体分布。 扫描桶时，比较相邻非空桶的间距，用动态规划思想更新最大差值。