We have a collection of stones, each stone has a positive integer weight.
Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)
 
Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
 
Note:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Difficulty: introductory

Starter code:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        

Solutions:
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while True:
            if len(stones) == 1:
                return stones[0]
            if len(stones) == 0:
                return 0
            stones.sort()
            x = stones.pop()
            y = stones.pop()
            if y != x:
                stones.append(x-y)
            


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        ls = len(stones)
        if ls == 1:
            return stones[0]
        elif ls == 0:
            return 0
        stones.sort(reverse=True)
        while len(stones) > 1:
            stone1 = stones.pop(0)
            stone2 = stones.pop(0)
            if not stone1 == stone2:
                stone1 -= stone2
                stones.insert(0, stone1)
                stones.sort(reverse=True)
        try:
            return stones[0]
        except IndexError:
            return 0

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while len(stones) > 1:
            firstMax,secMax =stones.pop(stones.index(max(stones))),stones.pop(stones.index(max(stones)))
            if firstMax - secMax != 0:
                stones.append(firstMax - secMax)
        if stones:
            return stones[0]
        else:
            return 0

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        
        
        
        while(len(stones) > 1):
            stones.sort(reverse=True)
            stones[0] = stones[0] - stones[1]
            del stones[1]
        
        if(len(stones) == 1):
            return stones[0]
        return 0


from heapq import heappop, heappush, heapify 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i in range(len(stones)):
            stones[i] *= -1
            
        # min heapify
        heapify(stones)
        while(len(stones) > 1):
            # get the max
            max1 = heappop(stones)
            max2 = heappop(stones)
            if -max1 - (-max2) > 0:
                heappush(stones, -(-max1 - (-max2)))
            # remove the max
            # get the max2
            # remove the max2
            
            
                # add -(-max1 - (-max2)) to the stones
        
        if len(stones) == 1:
            return -stones[0]
        return 0


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # while len(stones) > 1:
        #     stones.sort()
        #     num = stones.pop() - stones.pop()
        #     stones.append(num)
        # return 0 if len(stones) == 0 else stones[0]
        
        heap = [-x for x in stones]
        heapq.heapify(heap)
        while len(heap) > 1 and heap[0] != 0:
            heapq.heappush(heap, heapq.heappop(heap) - heapq.heappop(heap))
        return - heap[0]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        i = max(stones)
        weights = [0]*(i+1)
        for stone in stones:
            weights[stone] += 1
        current = 0
        while i > 0:
            if weights[i] != 0:
                if current == 0:
                    current = i
                    weights[i] -= 1
                else:
                    current -= i
                    weights[i] -= 1
                    if current > i:
                        i = current
                    weights[current] += 1
                    current = 0
            else:
                i -=1
        return current

import queue
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:

        heap = queue.PriorityQueue()
        for stone in stones:
            heap.put(-stone)
        
        while heap.qsize() > 1:
            num1 = heap.get()
            num2 = heap.get()
            
            heap.put(num1-num2)
            
        return -heap.get()

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-s for s in stones]
        heapq.heapify(stones)
        while len(stones) > 1:
            s1 = heapq.heappop(stones)
            s2 = heapq.heappop(stones)
            if s1 != s2:
                s = s1-s2
                heapq.heappush(stones, s)
                
        return -stones.pop() if stones else 0


class Solution:
    def lastStoneWeight(self, st: List[int]) -> int:
        for i in range(len(st)):
            st[i]*=-1
        heapq.heapify(st);
        while(len(st)>1):
            a,b=heapq.heappop(st),heapq.heappop(st);
            a*=-1;b*=-1
            if(b!=a):
                heapq.heappush(st,b-a)
        return -1*st[0] if len(st)==1 else 0