原题链接在这里:
题目:
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
- Constraints:
- 1 <= sticks.length <= 10^4
- 1 <= sticks[i] <= 10^4
题解:
- Find the routine that add the two smallest first, then largest repeated the least times.
- Use min heap to get two 2 smallest values, merge them and add merged back to min heap unitl there is only one stick in min heap.
- Time Complexity: O(nlogn). n = sticks.length.
- Space: O(n).
- AC Java:
- class Solution {
- public int connectSticks(int[] sticks) {
- if(sticks == null || sticks.length <2){
- return 0;
- }
- PriorityQueue<Integer> minHeap = new PriorityQueue<>();
- for(int num : sticks){
- minHeap.add(num);
- }
- int res = 0;
- while(minHeap.size()> 1){
- int merge = minHeap.poll() + minHeap.poll();
- res += merge;
- minHeap.add(merge);
- }
- return res;
- }
- }
来源: http://www.bubuko.com/infodetail-3373708.html