Posted on 2023-04-24 20:22
Uriel 閱讀(53)
評論(0) 編輯 收藏 引用 所屬分類:
模擬 、
數據結構 、
閑來無事重切Leet Code
有一堆石子，每次取其中最大重量的兩顆，若重量一樣，則兩顆都消失，否則其中一顆消失，另一顆重量變為兩者重量之差，問最后剩下的石頭重量多少，用priority queue直接模擬即可
1 #1046
2 #Runtime: 29 ms (Beats 83.46%)
3 #Memory: 13.9 MB (Beats 47.65%)
4
5 class Solution:
6 def lastStoneWeight(self, stones: List[int]) -> int:
7 hp = []
8 for st in stones:
9 heapq.heappush(hp, -st)
10 while len(hp) >= 2:
11 s1 = heapq.heappop(hp)
12 s2 = heapq.heappop(hp)
13 if s2 > s1:
14 heapq.heappush(hp, s1 - s2)
15 return abs(hp[0]) if hp else 0