1046. Last Stone Weight

Question: Last Stone Weight

Solution

想法：

找最重的兩個 → 排序取最大兩個，會有兩種可能

1. x ≠ y 需要再插入新的值
2. x == y 不需要再插入新的值

需要一個 data structure 可以快速取出最大值，移除掉，再插入新的值 → Max Heap

• 取出最大 O(1)
• 移除最大 O(log n)
• 插入新的值 O(log n)

TimeComplexity: O(n * log n) 因為要取出 max n 次 = n * log n

因為 python 沒有 Max heap 只有 min heap

用 min heap 模擬 max heap 的作法就是，把所有的 element * -1 存起來，pop 時，pop 出來的數字 * -1 就會是原來的最大值

import heapq

class Solution:

def lastStoneWeight(self, stones: list[int]) -> int:

stones = [ -s for s in stones]

heapq.heapify(stones)

print(stones)

while len(stones) > 1:

first = heapq.heappop(stones) # -8

second = heapq.heappop(stones) # -7

if second > first:

heapq.heappush(stones, first - second)

stones.append(0)

return abs(stones[0])

Video Solution