1167. 连接木棍的最低费用

ITCharge大约 4 分钟

---

1167. 连接木棍的最低费用

标签：贪心、数组、堆（优先队列）
难度：中等

题目链接

1167. 连接木棍的最低费用 - 力扣

题目大意

描述：给你一堆长度不同的木棍，每次可以选两根连在一起，花费的力气就是两根木棍的长度之和。连完后，这两根木棍就变成了一根更长的木棍。重复这个过程，直到所有木棍都连成一根。

要求：返回把所有木棍连成一根所需的最小总花费。

说明：

木棍数量范围： $1 \le sticks.length \le 10^4$ 。
每根木棍的长度范围： $1 \le sticks[i] \le 10^4$ 。

示例：

示例 1：

输入：sticks = [2,4,3]
输出：14
解释：从 sticks = [2,4,3] 开始。
1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4]
2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9]
所有木棍已经连成一根，总费用 5 + 9 = 14

示例 2：

输入：sticks = [1,8,3,5]
输出：30
解释：从 sticks = [1,8,3,5] 开始。
1. 连接 1 和 3 ，费用为 1 + 3 = 4 。现在 sticks = [4,8,5]
2. 连接 4 和 5 ，费用为 4 + 5 = 9 。现在 sticks = [9,8]
3. 连接 9 和 8 ，费用为 9 + 8 = 17 。现在 sticks = [17]
所有木棍已经连成一根，总费用 4 + 9 + 17 = 30

解题思路

思路 1：贪心 + 最小堆

为什么每次都选最短的？ 每次连接的花费会累加到总成本中，而连接后的新木棍又会参与后续连接。如果一根木棍比较长，我们希望它被连接的次数尽可能少（因为它每次参与都会带来较大花费）。最短的木棍参与连接的次数越多越好，因为每次带来的花费小。这就是典型的哈夫曼编码思想。

具体做法：用「最小堆」（也叫优先队列）来帮我们快速找到当前最短的两根木棍。

拆解步骤：

把所有木棍长度放进最小堆——最小堆的特点是：不管什么时候问它，它都能立刻告诉我们当前最小的数是多少。
循环执行「取两根最短的 → 连接 → 放回去」：只要堆里还有超过一根木棍，就重复做这三件事：
- 从堆顶取出最短的那根木棍
- 再从堆顶取出第二短的那根木棍
- 计算这两根的长度之和，累加到总花费中
- 把连接后的新木棍放回堆里
堆里只剩一根木棍时，结束——这时候所有木棍已经连成一根了，返回累加的总花费即可。

为什么用最小堆？ 因为每次操作后，连接产生的新木棍长度不一定是当前最短的，我们需要一种能随时插入新元素、又能随时取出最小值的结构。最小堆的「插入」和「取出最小值」操作都只需要 $O(\log n)$ 时间，效率很高。

思路 1：代码

import heapq

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        # 把木棍长度数组变成最小堆（原地建堆）
        heapq.heapify(sticks)

        total_cost = 0

        # 只要还剩超过一根木棍，就要继续连接
        while len(sticks) > 1:
            # 从堆中取出最短的两根木棍
            first = heapq.heappop(sticks)
            second = heapq.heappop(sticks)

            # 连接这两根，花费计入总成本
            cost = first + second
            total_cost += cost

            # 连接后的新木棍放回堆里，等待后续继续连接
            heapq.heappush(sticks, cost)

        return total_cost

思路 1：复杂度分析

时间复杂度： $O(n \log n)$ 。用人话说就是：如果一开始有 $n$ 根木棍，我们需要进行 $n-1$ 次连接操作。每次操作都要从堆里取两次和放回一次，每次耗时 $\log n$ 。建堆只需要 $O(n)$ ，所以总时间大约是 $n$ 乘以 $\log n$ 。
空间复杂度： $O(1)$ 。我们没有使用额外的存储空间，因为直接在输入数组上建堆，用的是原地操作。