1046. Last Stone Weight

Easy

Problem:

Given an array of integers representing the weights of stones, you repeatedly smash the two heaviest stones together. If their weights are equal, both are destroyed; if not, the heavier stone's new weight is the difference between the two. Continue this process until at most one stone remains, and return its weight. If no stones are left, return 0.

Solution:

Using a min heap, implement a max heap.

heapq

Reference to heapq: Heap queue (or heapq) in Python

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        inverted = [-i for i in stones]
        heapq.heapify(inverted)

        while len(inverted) > 1:
            first = heapq.heappop(inverted)
            second = heapq.heappop(inverted)

            if second != first:
                heapq.heappush(inverted, -(abs(first)-abs(second)))


        return -inverted[0] if inverted else 0