1. 问题背景与核心挑战今天要拆解的是LeetCode第3010题将数组分成最小总代价的子数组 I的排序解法。这道题在周赛中出现时让不少选手栽了跟头——看似简单的数组分割问题实则暗藏玄机。题目给定一个整数数组nums要求将其分成若干子数组使得所有子数组的代价之和最小。这里的代价定义为子数组中最大值与最小值的差。举个例子对于数组[3,1,2,4]如果分成[3,1]和[2,4]两个子数组第一个子数组代价 max(3,1) - min(3,1) 2第二个子数组代价 max(2,4) - min(2,4) 2 总代价就是2 2 4但这不是最优解因为如果分成[3,1,2]和[4]总代价只有(3-1)(4-4)2。这就是我们需要解决的优化问题。2. 排序解法的直觉与证明2.1 为什么排序能解决问题当我第一次看到这个问题时直觉告诉我排序可能会是关键。经过几次尝试后发现将数组排序后相邻元素的差值最小。这意味着如果我们把排序后的数组分成若干连续段每段的最大最小值差即代价会相对较小。数学证明如下 假设最优解中存在一个子数组包含非连续元素即存在a ≤ b ≤ c且b不在该子数组而a、c在。此时该子数组的代价至少为c-a。但如果把b也包含进来代价仍然是c-a因为最大值和最小值不变但可能减少其他子数组的代价。因此最优解必然由排序后的连续子数组构成。2.2 排序后的分割策略将数组升序排序后问题转化为在排序后的数组中寻找k-1个分割点将数组分成k段使得各段首尾差值之和最小。这里的k是题目要求的子数组数量。例如对于排序后的[1,2,3,4]要分成2段分割点在1|2 3 4代价(1-1)(4-2)2分割点在1 2|3 4代价(2-1)(4-3)2分割点在1 2 3|4代价(3-1)(4-4)2可以看到无论怎么分割总代价都是2。这说明对于均匀分布的数组分割点位置不影响结果。3. 算法实现细节3.1 完整算法步骤排序数组首先对原数组进行升序排序nums.sort()计算相邻差值计算排序后相邻元素的差值diffs [nums[i1] - nums[i] for i in range(len(nums)-1)]选择分割点我们需要选择k-1个分割点这些分割点应该跳过最大的m个差值m len(nums)-k因为跳过大的差值意味着不在这里分割可以减少总代价# 要分成k个子数组需要k-1个分割点 # 相当于选择n-1个相邻差值中最小的k-1个 diffs.sort() return sum(diffs[:k-1])3.2 复杂度分析时间复杂度O(n log n)主要来自排序操作空间复杂度O(n)存储差值数组可以优化到O(1)3.3 边界情况处理在实际编码中需要处理以下特殊情况当k1时整个数组作为一个子数组代价就是max(nums)-min(nums)当k≥n时每个元素单独成组总代价为0空数组情况题目通常不会出现4. 代码实现与优化4.1 Python完整实现def minCost(nums, k): if k 1: return max(nums) - min(nums) if k len(nums): return 0 nums.sort() diffs [nums[i1] - nums[i] for i in range(len(nums)-1)] diffs.sort() return sum(diffs[:k-1])4.2 空间优化版本我们可以避免存储所有差值只需要跟踪最小的k-1个差值import heapq def minCostOptimized(nums, k): if k 1: return max(nums) - min(nums) if k len(nums): return 0 nums.sort() min_heap [] for i in range(len(nums)-1): diff nums[i1] - nums[i] if len(min_heap) k-1: heapq.heappush(min_heap, -diff) # 用最大堆模拟最小堆 else: if -min_heap[0] diff: heapq.heappop(min_heap) heapq.heappush(min_heap, -diff) return sum(-x for x in min_heap)这个版本的空间复杂度降到了O(k)在k远小于n时有优势。5. 与其他解法的对比5.1 动态规划解法这道题也可以用动态规划解决定义dp[i][j]表示前i个元素分成j组的最小代价。状态转移方程为 dp[i][j] min(dp[m][j-1] cost(m1,i)) for m from j-1 to i-1其中cost(l,r)表示子数组nums[l..r]的代价最大值减最小值。这种解法时间复杂度为O(n²k)在n较大时效率明显低于排序解法。5.2 贪心选择证明我们的排序解法本质上是一种贪心算法——每次选择最小的相邻差值作为分割点。这种选择的正确性基于以下性质总代价等于所有未被选作分割点的相邻差值之和要最小化总代价就应该选择最大的m个相邻差值不作为分割点即选择最小的k-1个差值作为分割点6. 常见错误与调试技巧6.1 典型错误案例忽略k1的特殊情况# 错误实现 def minCost(nums, k): nums.sort() diffs [nums[i1] - nums[i] for i in range(len(nums)-1)] diffs.sort() return sum(diffs[:k-1]) # 当k1时diffs[:0]为空返回0而实际应为max-min错误理解分割点数量分成k个子数组需要k-1个分割点有些同学会误以为是选择k个最小差值6.2 调试技巧小规模测试用例print(minCost([1,3,2,4], 2)) # 应返回2 print(minCost([1,3,2,4], 3)) # 应返回1 print(minCost([1,1,1,1], 2)) # 应返回0可视化分割过程 对于数组[1,2,3,4,5]和k3排序后[1,2,3,4,5]相邻差值[1,1,1,1]选择k-12个最小差值任意两个1分割方式1|2|3 4 5 → 代价(1-1)(2-2)(5-3)21 2|3|4 5 → 代价(2-1)(3-3)(5-4)2 所有分割方式代价相同7. 算法扩展与应用7.1 变种问题带权重的代价计算如果每个子数组的代价不是简单的max-min而是(max-min)×长度该如何解决这种情况下排序解法不再适用可能需要考虑动态规划。7.2 实际应用场景这类数组分割问题在实际中有广泛应用资源分配将任务分成若干组使各组执行时间差异最小数据分片数据库水平分片时使各分片数据量均衡机器学习决策树构建时的特征离散化过程7.3 进阶挑战LeetCode上类似题目分割数组的最大值Hard分隔数组以得到最大和Medium分割回文串 IIIHard这些题目都可以用类似的分割优化思路来解决但具体实现各有不同。