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

Source: leetcode | Difficulty: EASY
Tags: Data structures

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
		heapify(stones)
		while len(stones) > 1:
			max1 = heappop(stones)
			max2 = heappop(stones)
			if -max1 - -max2 > 0:
				heappush(stones, -(-max1 - -max2))
		if len(stones) == 1:
			return -stones[0]
		return 0


class Solution:

	def lastStoneWeight(self, stones: List[int]) -> int:
		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