Posted on 2023-04-24 20:22
Uriel 阅读(25)
评论(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