LEETCODE 1167. Minimum Cost to Connect Sticks 解题思路分析

题目大意：

连接棒材的最低费用

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y.  You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

示例 1:

输入: sticks = [2,4,3]
输出: 14

示例2:

输入: sticks = [1,8,3,5]
输出: 30

提示:

• 1 <= sticks.length <= 10^4
• 1 <= sticks[i] <= 10^4

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1167

解题思路分析：

这道题需要一点贪心思想，我们直接来举例说明一下。比如数组为：

[1,8,3,5]

先不考虑最优解，直接按顺序连接的话，应该是以下步骤：

1 + 8 = 9 // All cost = 9
9 + 3 = 12 // All cost = 9 + 12 = 21
12 + 5 = 17 // All cost = 21 + 17 = 38

总花费（All cost）的变化是从9 -> 21 -> 38。也许这样看还不是太直观，我们再详细看下这些数字是怎么组成的：

9 = (1 + 8);
21 = 9 + 12 = (1 + 8) + ((1 + 8) + 3);
38 = 21 + 17 = ((1 + 8) + ((1 + 8) + 3)) + (((1 + 8) + 3) + 5);

我们不难发现，越早被加入的数字，在最后的结果中它被累加的次数就越多，因此，我们应该将更小的数字放在前面被累加才能得到最优解。

解题时，我们可以从集合中选出2个最小的数字进行累加，累加后，将和加入返回结果，另外将这两个最小的数字删除，并将其累加结果放入到集合，重复上述步骤，再选出2个最小的累加，直到集合中只剩下一个数字为止。这种解法与哈夫曼树的算法比较类似。

之前做过一道hard题目，思路与本题很相似，如果本题弄明白了， 大家可以挑战一下 LEETCODE 1199. Minimum Time to Build Blocks 解题思路分析 这道题目。

实现代码：

public int connectSticks(int[] sticks) {
    // 将数组中所有数字放入Queue中。
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for(int s : sticks) q.offer(s);
    // 返回结果
    int res=0;
    // 当存在2个棒材或以上时，不断地合并
    while(q.size()>1){
        // 取出2个cost最小的合并
        int cost=q.poll()+q.poll();
        // 将合并cost加入返回结果
        res+=cost;
        // 将合并后的棒材加入Queue
        q.offer(cost);
    }
    return res;
}

本题解法执行时间为40ms。

Runtime: 40 ms, faster than 93.51% of Java online submissions for Minimum Cost to Connect Sticks.

Memory Usage: 38.9 MB, less than 100.00% of Java online submissions for Minimum Cost to Connect Sticks.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1167-minimum-cost-to-connect-sticks-解题思路分析/