【Leetcode】1167. Minimum Cost to Connect Sticks

题目地址：

https://leetcode.com/problems/minimum-cost-to-connect-sticks/

给定一个长 n n n数组 A A A，每次可以合并 a a a和 b b b两个数成为一个新数 a + b a+b a+b，需要的花费是 a + b a+b a+b。要将 A A A里的数都合并成一个。问最终总花费最少是多少。

每次都合并最小的两个数即可。证明参考https://blog.csdn.net/qq_46105170/article/details/109214982。代码如下：

import java.util.PriorityQueue;

public class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) {
            minHeap.offer(stick);
        }
        
        int res = 0;
        while (minHeap.size() >= 2) {
            int x = minHeap.poll(), y = minHeap.poll();
            res += x + y;
            
            minHeap.offer(x + y);
        }
        
        return res;
    }
}
           

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，空间 O ( n ) O(n) O(n)。