[Java/Python 3] easy code using PriorityQueue/heapq w/ brief explanation and analysis.
Sort stones descendingly in PriorityQueue, then pop out pair by pair, compute the difference between them and add back to PriorityQueue.\n\nNote: since we alrea
Sort stones descendingly in PriorityQueue, then pop out pair by pair, compute the difference between them and add back to PriorityQueue.\n\nNote: since we already know the first poped out is not smaller, it is not necessary to use Math.abs().\n\n```java\n    public int lastStoneWeight(int[] stones) {\n    //  PriorityQueue<Integer> pq = new PriorityQueue<>(stones.length, Comparator.reverseOrder());\n        var q = new PriorityQueue<Integer>(stones.length, Comparator.reverseOrder());  // Credit to @YaoFrankie.\n        for (int st : stones) { \n            q.offer(st); \n        }\n        while (q.size() > 1) {\n            q.offer(q.poll() - q.poll());\n        }\n        return q.peek();\n    }\n```\n```\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        q = [-stone for stone in stones]\n        heapq.heapify(q)\n        while (len(q)) > 1:\n            heapq.heappush(q, heapq.heappop(q) - heapq.heappop(q))\n        return -q[0]\n```\n\nIn case you want to optimize the time performance, refer to the following version, which does NOT put `0` into the PriorityQueue:\n```java\n    public int lastStoneWeight(int[] stones) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>(stones.length, Comparator.reverseOrder());\n        IntStream.of(stones).forEach(pq::offer);\n        while (pq.size() > 1) {\n            int diff = pq.poll() - pq.poll();\n            if (diff > 0) {\n                pq.offer(diff);\n            }\n        }\n        return pq.isEmpty() ? 0 : pq.poll();\n    }\n```\n```python\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        heapify(hp := [-s for s in stones])\n        while len(hp) > 1:\n            if (diff := heappop(hp) - heappop(hp)) != 0:\n                heappush(hp, diff)\n        return -heappop(hp) if hp else 0\n```\n\n**Analysis:**\n\nTime: O(nlogn), space: O(n), where n = stones.length.\n\n----\n\n**Q & A:**\n\nQ: If not adding zeroes in the queue when polling out two elements are equal, is the result same as the above code?\n\nA: Yes. 0s are always at the end of the PriorityQueue. No matter a positive deduct 0 or 0 deduct 0, the result is same as NOT adding 0s into the PriorityQueue.
['Heap (Priority Queue)']