Solution 1 - Max Heap

Always smash the two heaviest stones.

TimeComplexity: O(n \log n)

SpaceComplexity: O(n)

""" 1046.1 - Last Stone Weight - Solution 1 - Max Heap """

import heapq
from typing import List

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

// Use BinaryHeap<i32>.
use std::collections::BinaryHeap;

fn last_stone_weight(stones: Vec<i32>) -> i32 {
	let mut h: BinaryHeap<i32> = stones.into_iter().collect();
	while h.len() > 1 {
		let y = h.pop().unwrap();
		let x = h.pop().unwrap();
		if y != x { h.push(y - x); }
	}
	h.pop().unwrap_or(0)
}
fn main() {}

1046 - Last Stone Weight

Solution 1 - Max Heap