难度: Medium
Submission
运行时间: 108 ms
内存: 17.0 MB
class Solution:
def connectSticks(self, sticks: List[int]) -> int:
if len(sticks) == 1:
return 0
heapq.heapify(sticks)
total_cost = 0
while len(sticks) > 1:
stick1 = heapq.heappop(sticks)
stick2 = heapq.heappop(sticks)
cost = stick1 + stick2
total_cost += cost
heapq.heappush(sticks, cost)
return total_cost
Explain
这个问题可以通过优先队列（最小堆）来解决。首先，将所有的木棍长度放入一个最小堆中。在每一步中，从堆中取出两个最短的木棍，并计算将它们连接起来的成本，即两者之和。将这个成本加入到总成本中，并把新形成的木棍（即两者之和）加回到最小堆中。这个过程一直重复，直到堆中只剩下一个木棍。这时，累计的总成本就是连接所有木棍的最低费用。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def connectSticks(self, sticks: List[int]) -> int:
# 如果只有一根木棍，无需连接，费用为0
if len(sticks) == 1:
return 0
# 将所有木棍长度转化为一个最小堆
heapq.heapify(sticks)
total_cost = 0 # 初始化总费用为0
# 当堆中至少有两根木棍时，执行合并操作
while len(sticks) > 1:
stick1 = heapq.heappop(sticks) # 取出最小的木棍
stick2 = heapq.heappop(sticks) # 取出次小的木棍
cost = stick1 + stick2 # 计算合并的费用
total_cost += cost # 累加到总费用
heapq.heappush(sticks, cost) # 将新形成的木棍放回堆中
return total_cost # 返回总费用
Explore
在这个问题中，我们需要频繁地找到并移除最小的元素，然后插入新的元素。使用最小堆（优先队列）可以有效地支持这些操作。最小堆能够在常数时间O(1)内提供最小元素，并且可以在对数时间O(log n)内完成删除最小元素和插入新元素的操作。相比之下，如果使用数组或链表，我们需要O(n)的时间来找到最小元素，插入操作也可能需要O(n)的时间（尤其是在数组中需要保持顺序时），这使得整体效率较低。因此，为了优化性能，选择最小堆是更合理的选择。
如果在合并时取出的两根木棍长度相同，这并不会对算法的总体逻辑或成本计算产生特殊影响。无论木棍的长度是否相同，合并的成本都是两根木棍的长度之和。因此，这种情况只是一个特殊实例，但并不改变合并操作的基本成本计算或结果。
将新形成的木棍加回到最小堆中确实需要重新调整堆来维持堆的性质，这是通过堆的上浮或下沉操作完成的，通常需要O(log n)时间。虽然这种操作涉及到堆的重构，但这是最小堆设计用来处理此类场景的，且是高效的。最小堆的整体结构使其非常适合频繁地进行插入和删除最小元素的操作，因此，虽然每次合并操作都需要堆的重构，但这并不会超出最小堆处理此类问题的性能预期。
这个算法的目标是每次找到并合并最短的两根木棍，这种贪心策略确保了每一步的局部最优解，并最终达到全局最优的总成本。独立于木棍的初始排列顺序，这种方法通过确保每次操作都是成本最低的合并，从而达到整体成本最低。因此，总是存在一个最佳方案使得总成本最小，而这个结果不依赖于木棍的初始排列顺序。