1046. Last Stone Weight

 一刷 06/2022

Version #1 MaxHeap

Time O(NlogN)

Space O(N)

Runtime: 2 ms, faster than 75.94% of Java online submissions for Last Stone Weight.

Memory Usage: 42.3 MB, less than 6.13% of Java online submissions for Last Stone Weight.

class Solution {

    public int lastStoneWeight(int[] stones) {

        if (stones == null || stones.length == 0) {

            return 0;

        }

        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int stone : stones) {

            maxHeap.offer(stone);

        }

        while (maxHeap.size() >= 2) {

            int s1 = maxHeap.poll();

            int s2 = maxHeap.poll();

            if (s1 != s2) {

                maxHeap.offer(Math.abs(s1 - s2));

            }

        }

        if (maxHeap.isEmpty()) {

            return 0;

        }

        return maxHeap.poll();

    }

}