Last Stone Weight
- 1 min read
- LC-Easy
- Binary-heap
3 years ago
Solution
- Just use a heap
- Make number negative since python's heapq is a min heap.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def lastStoneWeight(self, stones: List[int]) -> int:
stones = list(map(lambda x: -x, stones))
heapify(stones)
while len(stones) > 1:
x, y = heappop(stones), heappop(stones)
if x != y:
heappush(stones, x - y)
return abs(stones[0]) if stones else 0