# leetcode解題：(Easy) 1046. Last Stone Weight

題目：[https://leetcode.com/problems/last-stone-weight/](https://leetcode.com/problems/last-stone-weight/)

描述：輸入許多石頭對應的重量，每次拿重量最重的2顆石頭互砸會剩下重量相減後的一顆石頭，算出最後剩的一顆石頭的重量，石頭沒有剩則回傳`0`

解題思路：要有效率的找出最大的2顆石頭可以使用排序，但是每次2顆最大的石頭砸完後還是得要把新的石頭排到對應的位置，這樣的時間複雜度會是(每次砸完重新排序的)`O(nlogn)`乘上(一共要砸的次數)`O(n)`的`O(n^2logn)`
因此我們改用更快的heap，heap插入新元素的時間複雜度為`O(logn)`，取出最大值為`O(1)`，每次取出石頭砸完再將剩的石頭放回去heap，時間複雜度就能降為(每次砸完放回去的)`O(logn)`乘上(一共要砸的次數)`O(n)`的`O(nlogn)`

程式碼：

class Solution {
    public int lastStoneWeight(int[] stones) {
        //outputs largest number
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());

        for(int stone : stones) {
            queue.offer(stone);
        }

        while(queue.peek() != null) {
            int bigStone = queue.poll();
            if(queue.peek() == null) return bigStone;
            int smallStone = queue.poll();

            queue.offer(bigStone - smallStone);
        }

        return 0;
    }
}

時間複雜度：`O(nlogn)`
空間複雜度：`O(n)`

###### tags: `leetcode` `easy` `heap`