You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x &lt;= y. The result of this smash is:


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


At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

&nbsp;
Example 1:

Input: stones = [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 the last stone.


Example 2:

Input: stones = [1]
Output: 1


&nbsp;
Constraints:


	1 &lt;= stones.length &lt;= 30
	1 &lt;= stones[i] &lt;= 1000


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

        while len(stones) > 1:
            mx1 = -heapq.heappop(stones)
            mx2 = -heapq.heappop(stones)
            if mx1 - mx2:
                heapq.heappush(stones, -(mx1 - mx2))

        if len(stones):
            return -heapq.heappop(stones)
        return 0
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((x,y) -> Integer.compare(y,x));
        for (int i = 0; i < stones.length; i++) {
            pq.add(stones[i]);
        }
        while (pq.size() > 1) {
            int r1 = pq.poll();
            int r2 = pq.poll();
            if (r1 != r2) pq.add(r1 - r2);
        }
        return (pq.isEmpty()) ? 0 : pq.poll();
    }
}
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        while(stones.size()>1){
            sort(stones.begin(), stones.end(), greater<int>());
            stones[1] = (stones[0]-stones[1]);
            stones.erase(stones.begin());
        }
        return stones[0];
    }
};
var lastStoneWeight = function(stones) {
    let first = 0, second = 0;
    stones.sort((a,b) => a - b);
    while(stones.length > 1) {
        first = stones.pop();
        second = stones.pop();
        stones.push(first - second);
        stones.sort((a,b) => a - b);
    }
    return stones[0];
};
Last Stone Weight