Last Stone Weight
你有一堆石头，stones[i] 表示第 i 块石头的重量。每一轮，取出最重的两块石头并将它们撞在一起。如果它们重量相同，两块石头都会被销毁。否则，较轻的石头被销毁，较重的石头重量减去两者重量之差。
编写 lastStoneWeight，让它持续进行多轮操作，直到剩下不超过一块石头，并返回这块石头的重量；如果没有剩下石头，则返回 0。
函数
- stonesinteger-array
- 石堆中石头的重量
- 返回值integer
- 最后一块石头的重量，如果没有剩余石头则为 0
约束条件
1 ≤ stones.length ≤ 1041 ≤ stones[i] ≤ 1000
示例
- 输入
- stones = [3, 9, 4, 6, 2]
- 输出
- 0
- 解释
9和6剩下3，接着4和3剩下1，然后3和2又剩下一个1。两个1相互抵消，所以答案是0。
- 输入
- stones = [10, 4, 1]
- 输出
- 5
- 解释
10和4相减后剩下6，6和1相减后剩下5。还剩下一块石头，重量为5。
- 输入
- stones = [8]
- 输出
- 8
- 解释
- 一块石头没有其他石头可以与之碰撞，所以它的重量
8就是答案。
进阶
重量最大为 1000。你能利用这个上限，在不使用堆的情况下，以 O(n + W) 的时间完成吗？其中 W 是最大的重量。
提示
逐个打开提示，每个都会多透露一点。
按照描述完成这些回合。每回合开始时，你需要快速找到什么？
每一轮都需要取出两块最重的石头，而且放回去的石头可能比堆里已有的石头轻。即使有新值加入，也能随时知道最大值的数据结构，可以让你不必重新排序。
把所有石头放入最大堆。弹出两次，如果差值不为零，就将差值放回堆中，然后重复此过程，直到最多只剩下一块石头。返回这块石头，或者返回
0。
题解
没有捷径可以跳过步骤：你需要玩完每一轮。每一轮都要从不断变化的一堆石头中取出最重的两块，因为被砸碎的石头可能会以更轻的重量重新加入。最大堆能取出最重的石头，并在 O(log n) 时间内放回一块新石头。
每回合都对堆进行排序
结果正确，但无法在最大的测试中运行完毕
思路
严格按照规则操作：将石头堆排序，从末尾取出最重的两块，如果它们的重量差不为 0，就把差值放回去。每一轮都要重新排序，因为差值可能出现在任何位置。在第一个示例中，9 和 6 产生的差值是 3，它应该排在 4 的前面。
每一轮至少会移除一块石头，因此最多有 n-1 轮，每轮最多对 n 块石头排序：O(n² log n)。当 n = 10^4 时，这相当于最多进行 10^4 次排序，每次排序最多处理 10^4 个数字。
算法
- 将这些石头复制到名为
pile的列表中。 - 当列表中有多于一块石头时，按升序排序。
- 取出最后两块石头，
heaviest和second。 - 如果它们不相等，就把
heaviest - second放回列表。 - 返回剩下的石头；如果列表为空，则返回
0。
def lastStoneWeight(stones):
pile = list(stones)
while len(pile) > 1:
pile.sort() # the two heaviest stones move to the end
heaviest = pile.pop()
second = pile.pop()
if heaviest != second:
pile.append(heaviest - second)
return pile[0] if pile else 0最大堆
思路
最大堆会将最大值保存在堆顶，移除堆顶元素或添加一个值的时间开销为 O(log n)。将每块石头都放入堆中。每一轮，弹出两次，取出最重的两块石头；如果它们的差不为零，就将差值放回堆中，堆会自动将它放到合适的位置。对于 [10, 4, 1]，先弹出 10 和 4，再放入 6；然后弹出 6 和 1，再放入 5。
最多会有 n-1 轮，每轮执行两次弹出和一次放入，因此时间复杂度为 O(n log n)，空间复杂度为 O(n)。对于没有内置堆的语言，答案会用数组来保存堆，索引 i 的父节点位于 (i-1)/2。
算法
- 将每块石头放入最大堆中。
- 当堆中石头多于一块时，取出最重的石头，然后取出第二重的石头。
- 如果两块石头重量不同，就压入
heaviest - second。 - 返回堆顶元素；如果堆为空，则返回
0。
import heapq
def lastStoneWeight(stones):
# heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
heap = [-w for w in stones]
heapq.heapify(heap)
while len(heap) > 1:
heaviest = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if heaviest != second:
heapq.heappush(heap, -(heaviest - second))
return -heap[0] if heap else 0
易错点和边界情况
- 返回空堆的顶部。当最后两块石头的重量相同时，就像第一个示例中那样，什么也不剩，答案是
0。 - 意外地使用了最小堆。Python 的
heapq和 Java 默认的PriorityQueue都会取出最小值；你可以将重量取负，或传入反向比较器。 - 忘记了取负后的符号。取出的两个值都是负数，因此要推入的值是
-(heaviest - second)。 - 一开始排序一次，然后遍历列表。差值可能比你还没处理的石头更轻，因此第一轮之后，顺序就不再有效。
常见问题3
LastStoneWeight 的时间复杂度是多少？
使用最大堆，最多进行 n-1 轮，每轮执行两次弹出和一次推入，耗时 O(n log n)，空间复杂度为 O(n)。每轮都对整个堆排序，耗时为 O(n² log n)。
为什么在 Last Stone Weight 中使用堆，而不是排序后的列表？
排序列表可以一次给出两块最重的石头，但将差值重新插入并排序时，最多需要移动 n 个条目，在所有轮次中总计为 O(n²)。堆只需回答“最大值是什么”，并接受一个新值，这两种操作都只需 O(log n)，而模拟只需要这些操作。
粉碎重量相同的石头时，顺序会影响答案吗？
不。如果几块石头的重量都是最重的，那么无论你选哪两块，它们的重量都相同，所以这一轮结束后，石堆中的重量也一样。答案只取决于重量。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def lastStoneWeight(stones):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
stones = [3, 9, 4, 6, 2]
预期输出
0