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.

Example 1:

Input: sticks = [2,4,3]
Output: 14
           

Example 2:

Input: sticks = [1,8,3,5]
Output: 30
           

思路：用pq，每次poll出來最小的兩個，進行相加； Time: O(nlogn) Space: O(n)

class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (a - b));
        int cost = 0;
        for(int i = 0; i < sticks.length; i++){
            pq.offer(sticks[i]);
        }
        
        while(pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            cost += a + b;
            pq.offer(a + b);
        }
        return cost;
    }
}