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 完整算法步骤

1. 排序数组：首先对原数组进行升序排序

   nums.sort()

2. 计算相邻差值：计算排序后相邻元素的差值

   diffs = [nums[i+1] - nums[i] for i in range(len(nums)-1)]

3. 选择分割点：我们需要选择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 边界情况处理

在实际编码中需要处理以下特殊情况：

1. 当k=1时，整个数组作为一个子数组，代价就是max(nums)-min(nums)
2. 当k≥n时，每个元素单独成组，总代价为0
3. 空数组情况（题目通常不会出现）

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[i+1] - 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[i+1] - 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(m+1,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 典型错误案例

1. 忽略k=1的特殊情况：

   # 错误实现 def minCost(nums, k): nums.sort() diffs = [nums[i+1] - nums[i] for i in range(len(nums)-1)] diffs.sort() return sum(diffs[:k-1]) # 当k=1时，diffs[:0]为空，返回0，而实际应为max-min

2. 错误理解分割点数量：

   • 分成k个子数组需要k-1个分割点
   • 有些同学会误以为是选择k个最小差值

6.2 调试技巧

1. 小规模测试用例：

   print(minCost([1,3,2,4], 2)) # 应返回2 print(minCost([1,3,2,4], 3)) # 应返回1 print(minCost([1,1,1,1], 2)) # 应返回0

2. 可视化分割过程： 对于数组[1,2,3,4,5]和k=3：

   • 排序后：[1,2,3,4,5]
   • 相邻差值：[1,1,1,1]
   • 选择k-1=2个最小差值：任意两个1
   • 分割方式：
     • 1|2|3 4 5 → 代价=(1-1)+(2-2)+(5-3)=2
     • 1 2|3|4 5 → 代价=(2-1)+(3-3)+(5-4)=2 所有分割方式代价相同

7. 算法扩展与应用

7.1 变种问题：带权重的代价计算

如果每个子数组的代价不是简单的max-min，而是(max-min)×长度，该如何解决？这种情况下排序解法不再适用，可能需要考虑动态规划。

7.2 实际应用场景

这类数组分割问题在实际中有广泛应用：

1. 资源分配：将任务分成若干组，使各组执行时间差异最小
2. 数据分片：数据库水平分片时，使各分片数据量均衡
3. 机器学习：决策树构建时的特征离散化过程

7.3 进阶挑战

LeetCode上类似题目：

• 410. 分割数组的最大值（Hard）
• 1043. 分隔数组以得到最大和（Medium）
• 1278. 分割回文串 III（Hard）

这些题目都可以用类似的"分割+优化"思路来解决，但具体实现各有不同。