1046. Last Stone Weight - Easy

前往題目

想法

• 用priority queue

思路

這題無需考慮位置，因為最終回傳的也是剩下的weight，而不是哪顆石頭，所以非常簡單

1. 利用priority queue把stones存為descending order(降冪)
2. 然後把前兩項相減後的結果再加入pq(兩數都要poll)
3. 直到pq.size只剩1，直接回傳pq.poll()

題目說如果沒有石頭那就回傳0，而我沒判斷也AC，應該是因為我是用直接每個都兩兩相減，所以如果出現沒有石頭的局面那一定是最後兩顆石頭重量相等。因此最後pq裡的那個絕對是0，所以不用額外判斷。這個算是賽到的，一開始沒考慮到卻過了才發現

Code

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(
            Collections.reverseOrder()
        );

        // Add stone and sort
        for (int i = 0; i < stones.length; ++i) {
            pq.add(stones[i]);
        }

        while (pq.size() > 1) {
            pq.add(Math.abs(pq.poll() - pq.poll()));
        }

        return pq.poll();
    }
}