LeetCode风格问题优化：求服装尺寸唯一的最小成本算法

时间复杂度疑问确认 #

你的假设完全正确：原代码的最坏时间复杂度确实是O(n²)。

比如极端场景：所有元素的尺寸相同，且按成本降序处理（优先队列先取出成本最高的元素）。第一个元素占用初始尺寸，第二个元素需要递增1次，第三个递增2次……第n个元素需要递增n-1次。内层循环的总执行次数为1+2+…+(n-1) = n(n-1)/2，因此总时间复杂度为O(n²)，这就是部分用例超时的核心原因。

优化方案：并查集（路径压缩）+ 排序 #

我们可以用并查集（DSU）快速定位当前尺寸之后的第一个可用位置，将内层循环的O(k)操作优化为近似O(1)（路径压缩后），整体时间复杂度降至O(n log n)（主要来自排序步骤）。

核心思路 #

1. 优先处理高成本元素：和原思路一致，将(size, cost)按成本降序排序，让成本高的元素优先占用原尺寸（因为调整高成本元素的代价更大，应尽量避免）。
2. 并查集跟踪可用位置：用并查集维护每个尺寸的下一个可用位置。当某个尺寸被占用时，将其指向“下一个尺寸的可用位置”，后续查找时直接跳转到目标位置，无需逐个递增检查。

伪代码实现 #

// 带路径压缩的并查集查找函数
function find(x, parent):
    if x not in parent:
        parent[x] = x
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]

total_cost = 0
parent = {}  // 哈希表存储父节点，适配任意尺寸范围

// 将尺寸-成本对按成本降序排序
sorted_pairs = sorted(zip(size_array, cost_array), key=lambda pair: -pair[1])

for current_size, current_cost in sorted_pairs:
    // 找到当前尺寸对应的第一个可用位置
    target_size = find(current_size, parent)
    // 累加调整成本
    total_cost += (target_size - current_size) * current_cost
    // 更新当前可用位置的父节点为下一个尺寸的可用位置
    next_size = target_size + 1
    parent[target_size] = find(next_size, parent)

return total_cost

示例验证（对应题目给出的案例） #

输入：size = [3,3,4,5]，costs = [5,2,3,1]
排序后的处理顺序：(3,5) → (4,3) → (3,2) → (5,1)

1. 处理(3,5)：找到可用位置3，成本+0，将3的父节点设为find(4)=4。
2. 处理(4,3)：找到可用位置4，成本+0，将4的父节点设为find(5)=5。
3. 处理(3,2)：find(3) → 父节点是4，find(4) → 父节点是5，所以目标位置是5，成本+2*(5-3)=4。将5的父节点设为find(6)=6。
4. 处理(5,1)：find(5) → 父节点是6，目标位置是6，成本+1*(6-5)=1。
   总成本：4+1=5，和题目示例结果一致。

其他可选方案 #

如果不想用并查集，也可以用**有序集合（如Java的TreeSet、C#的SortedSet）**维护已占用的尺寸，通过ceiling或higher方法快速定位下一个可用位置，但每次查找的时间复杂度为O(log n)，整体仍为O(n log n)，效率略低于并查集。

内容的提问来源于stack exchange，提问作者user29783602