LeetCode-Python-1167. 连接棒材的最低费用

为了装修新房，你需要加工一些长度为正整数的棒材 sticks。

如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 由于施工需要，你必须将所有棒材连接成一根。

返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

提示：

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

思路：

类似LeetCode-Python-1130. 叶值的最小代价生成树，

本题应该就是亚麻的OA题了：

https://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=Mjk4NzE1fDA1YzQ2MmQ4Nzc4ZGI0YmU4NTlhYzA0MjI5MDk2NWYxfDE1NjM3MjU3MTc%3D&request=yes&_f=.png。

根据贪心的思想，应该把最长的棒子留到最后再合并，每次应该把当前最短的两根棒子合在一起。

所以是一个动态找最小值的过程，用优先级队列解题。

class Solution(object):
    def connectSticks(self, sticks):
        """
        :type sticks: List[int]
        :rtype: int
        """
        from heapq import * 
        heapify(sticks)
        res = 0
        while len(sticks) > 1:
            s1 = heappop(sticks)
            s2 = heappop(sticks)
            res += s1 + s2 #把最短的两根棒子合并在一起
            heappush(sticks, s1 + s2)
        return res