Leetcode1167 Minimum Cost to Connect Sticks

领扣地址本题在Leetcode上是会员题，对应Lintcode-1872

有若干长度为正整数的棍子，每连接两个棍子X和Y需要X+Y的代价，求问将所有棍子连接成一个的最小代价

因为连接两个棍子需要的代价是他们的长度和，合为一个之后又会再与其他棍子连接，相当于他们被重复计算了多次，为了减少代价，重复的长度必须要尽量小，所以很明显，每次取最小的两个棍子。

使用优先队列就迎刃而解了。

本题代码

public int MinimumCost(List<Integer> sticks) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(sticks);
    int ans = 0;
    while (pq.size() > 1) {
        int top = pq.poll();
        int top2 = pq.poll();
        ans += (top + top2);
        pq.offer(top + top2);
    }
    return ans;
}

注意点

C++中STL优先队列默认是大顶堆，队首是最大值

C++

// 小顶堆
priority_queue <int,vector<int>,greater<int> > q;
// 大顶堆（默认）
priority_queue <int,vector<int>,less<int> >q;
priority_queue<int> q;

Java中的优先队列默认是小顶堆，队首是最小值

Java若要实现大顶堆，重写Comparator函数

private static final int DEFAULT_INITIAL_CAPACITY = 11;
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(DEFAULT_INITIAL_CAPACITY, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {                
            return o2-o1;
        }
    });