1046_最后一块石头的重量

类型：堆

• 1046. 最后一块石头的重量 💚

  https://leetcode-cn.com/problems/last-stone-weight/

  ❓ 有一堆石头，重量都是正整数。每次从石堆中选出「两块最重的」石头，一起粉碎。如果两块石头一样重（x == y），那么二者都会被粉碎。如果其中一块较重(x > y)，那么较轻的石头将被粉碎完，更重的那块则质量变为 x - y。

  求最后剩下石头的重量，若无石头剩下，则返回 0.

  💡 堆

  构造大顶堆，每次从堆顶取出两块进行粉碎，剩下的再入堆。

  class Solution:
      def lastStoneWeight(self, stones: List[int]) -> int:
          if not stones:
              return 0
          if len(stones) == 1:
              return stones[0]
  
          # 将数组构造成大顶堆，每次从中取出最大的两个，再将二者的差值重新入堆，直至堆中只剩一个元素
          heap = [stone * -1 for stone in stones]
          heapq.heapify(heap)
          while len(heap) > 1:
              stone1 = - heapq.heappop(heap)
              stone2 = - heapq.heappop(heap)
              heapq.heappush(heap, -1 * abs(stone1 - stone2))
          return -1 * heap[0] if heap else 0

  时间复杂度：O(NlogN)，空间复杂度：O(N)