leetcode解題：(Easy) 1046. 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