难度: Easy
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
x == y，那么两块石头都会被完全粉碎；x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000运行时间: 20 ms
内存: 0.0 MB
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
if not stones:
return 0
if len(stones)==1:
return stones[0]
while stones:
stones = sorted(stones)
#print(stones, stones[-1], stones[-2])
diff = stones[-1]-stones[-2]
stones = stones[:-2]
if diff>0:
stones.append(diff)
#print(stones, '
')
if not stones:
return 0
if len(stones)==1:
return stones[0]
该题解采用的是一个简单直观的方法来解决问题。首先，如果石头堆为空或只有一块石头，直接返回对应的结果。否则，进入一个循环，不断排序并取出当前两块最重的石头进行对决。如果两块石头重量相同，则它们都被完全粉碎；如果不同，较小的一块将被完全粉碎，较大的一块的新重量将是二者的差值。这个过程重复，直到石头堆中剩下零块或一块石头。最后返回剩下的石头重量，或者如果没有石头剩下，则返回 0。
时间复杂度: O(n^2logn)
空间复杂度: O(1)
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
# Base cases: if no stones or only one stone, return 0 or the stone's weight
if not stones:
return 0
if len(stones)==1:
return stones[0]
# Continue until stones are available
while stones:
stones = sorted(stones) # Sort stones to find the two heaviest
diff = stones[-1]-stones[-2] # Find the difference between the heaviest and the second heaviest
stones = stones[:-2] # Remove the two heaviest stones
if diff>0:
stones.append(diff) # Add the resulting stone if any
if not stones:
return 0 # Return 0 if no stones left
if len(stones)==1:
return stones[0] # If one stone left, return its weight
在每个循环中进行排序并不是效率最优的方法，因为排序的时间复杂度为O(n log n)，而整个过程需要多次进行排序，使得总体时间复杂度较高。存在更高效的方法，例如使用最大堆（或优先队列）来管理石头。最大堆可以在O(log n)的时间内完成插入和删除最大元素的操作，因此在整个对决过程中维护石头的顺序会更加高效。使用最大堆，我们可以在总体时间复杂度为O(n log n)内完成整个问题的求解，其中n是石头的数量。
确实，按照题解的方法，每次处理两块石头后，新生成的石头的重量可能不再是列表中最大的，因此重新排序是必要的来保证每次都能处理最重的两块石头。这是题解所采用排序方法的一个必要步骤，以确保正确性。不过，如果使用最大堆作为数据结构，这个问题可以更高效地得到解决，因为最大堆会自动保证最大的元素总是可直接访问的。
在Python中，列表是一个动态数组，频繁地进行元素的添加和删除操作（特别是删除列表末端以外的元素）可能会导致额外的内存分配和数据移动，从而影响性能。在题解中，每次循环删除两个最重的石头并可能添加一个新的石头，这种操作确实可能使得性能受到影响。使用最大堆可以更有效地管理这种动态变化的数据集合，因为堆是为优化添加和删除最大元素的操作而设计的。
题解中的做法确实导致了不必要的重复排序，每次添加新的石头重量后都需要重新排序以找到新的两个最重的石头，这增加了算法的时间复杂度。更高效的数据结构是使用最大堆（或优先队列），它能够在保持内部元素顺序的同时，高效地处理元素的添加和删除操作。使用最大堆，每次可以直接访问最大元素，且插入新元素的时间复杂度为O(log n)，大大提高了效率。