『堆』最后一块石头的重量1046

题目相关

• 原题链接：1046. 最后一块石头的重量 - 力扣（LeetCode）
• 涉及知识：堆
• 题目难度：★

题目解读

根据题意，我们可以了解到需要不断地对一批正整数执行获取最大值并插入新值的操作，因而在此场景下使用堆排序（确切来说是大顶堆）最为高效。

Python相关

Python有一个内置库heapq专门就是用来执行最小堆的相关操作的，虽然没有直接替提供最大堆的实现，但我们稍加改造便可实现。

具体实现

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        temp = [-x for x in stones]
        heapq.heapify(temp) # 将数值变为对应负值并建立大顶堆
        while len(temp) > 1:
            x = heapq.heappop(temp) # 从堆中取出最小值（对应原最大数值）
            y = heapq.heappop(temp) # 从堆中取出次小值
            if x != y:
                heapq.heappush(temp, x - y) # 将新值入堆
        if temp:
            return -temp[0]
        return 0