技术提升是一个循序渐进的过程，所以我讲的leetcode算法题是从最简单的一级开始，然后到中级难度，最后以硬难度结束。目前我选择C语言、Python和Java作为实现语言，因为这三种语言比较典型。由于篇幅和精力有限，有兴趣实现其他语言的朋友请自行尝试。
如果你有任何问题，请在文章后评论或给我发私信。
如果有朋友要我谈其他话题，请在评论区留言或者给我发私信。
继续分享，敬请关注。
LeetCode 1046。最后的石头重量
问题描述：
我们收集了一些石头，每块石头的重量都是正整数。现在，需要选择两块最重的石头来压碎它们。假设它们的重量分别为X和Y，x=y，那么粉碎的结果是：如果x==y，它们都被一起完全破坏；如果x！=y，那么X的重量会被完全破坏，Y也会被破坏。X的重量过后，剩下的y-x会放回去。这样，最后只剩下一块石头了，石头的重量也回来了(如果没有剩下石头，就回到0)。附注：
1=石头，长度=30；1=石头[I]=1000；
示例：
00-1010解决问题的关键是如何找到两个最大权重。
因为每次你找到这两个最大重量，你都要把它们之间的差异算进去。所以如果差值不是0，可能会影响下一轮最大值搜索。(注意，如果两块石头的重量相同，它们的差值为0，说明没有剩下石头，所以再放回去，不会影响下一轮最大值搜索)
解决问题至少有三种方法。
第一种：排序
把石头按照从大到小的顺序排序，那么前两个数字就是最大的两个权重。计算完它们的差值后，扔进去继续下一轮排序。
请注意，每次操作后，要排序的元素数量会减少一个。
该算法的时间复杂度相对较高。
第二种：只取两个最大值。
从左到右，通过相互比较，只找到两个最大的权重，这样每次搜索的时间复杂度都是线性的。
算完出差价值后，把差额再扔回去，然后再去下一轮。
算法的复杂度为O(n ^ 2)，因为每轮运算后需要搜索的元素数量会少一个。
第三种：用最大的一堆。
关于最大堆，我们在前面的题目中用过。
最大的堆是二进制堆，这是一个完整的二叉树。其特点是，对于每个子树，其根节点都大于所有子节点。
为什么要用最大的一堆？因为得到最大堆的最大元素的复杂度是常数，它的插入复杂度是O(logn)。所以非常适合解决这个问题。
让我们专注于最大堆的实现。
1.二进制堆栈的结构
首先，我们定义函数heap_create，根据石头构造一个最大堆。它在内部调用heap_insert来插入特定的堆元素。
这种构造方法是每次向叶节点添加元素，然后让元素浮动。这种方法通常是有效的。浮动的原理是不断与父节点进行比较和替换的过程。具体原理图及说明请参考《第123篇》。
让我们解释一下最大堆的存储结构。正如我们前面所说的，因为最大堆是一个完整的二叉树，所以我们可以使用数组来存储二进制堆。下图显示了二进制堆和完整二叉树之间的对应关系：
可以看出，对于下标为x的元素，其左右子节点的下标分别为2x 1和2x 2；其父节点的索引为(x-1)/2。
有了这些信息，我们可以很容易地构建堆。
摧毁石头
桩建好之后，我们就开始破坏。
1).我们需要得到最大的两个元素，这很简单。最大堆的根节点(即堆数组的第一个元素)最大。我们可以通过两次弹出根元素来获得两个最大的元素。
但是，请注意，堆结构将在根节点每次弹出后被销毁。我们需要在每次弹出后重建堆结构，方法是：
当根弹出时，最后一个叶节点作为临时根节点复制到堆的起始位置，然后通过下沉重建堆结构。在这个过程中，新的最大元素将向上浮动，并最终成为新的根节点。
2).当我们得到两个最大的元素时，计算它们的差，并将差重新插入堆数组。
请注意，在此过程中，每销毁一块石头都会将堆大小减少一。(如果两块石头大小相同，我们可以认为只有一块会被破坏，它们相差的0会放回去，因为0不会影响最终结果)
我们重复这个销毁过程，直到堆大小为1，也就是说里面只有一块石头，只需要返回它的大小。
以下是该过程的示意图：
533ed56?from=pc">首先构造堆，构造完成后，分别弹出78和38，并重构堆结果，然后将它们的差，40放回到堆中。灰色的元素是这个过程中失效的元素。
详细代码如下：
最后留一个问题给大家：
这个用最大堆实现的算法，它的复杂度是多少？我估计90%的人会答错。
Java语言实现：
Java 的实现和C语言的实现一致，不再撰述。
代码如下：
Python语言实现：
我们用deapq来实现，由于deapq只支持最小堆，因此我们变通一下，构建堆的时候，插入重量的负值，这样构建的最小堆等价与最大堆。最后，获取最后石头重量的时候，不要忘了再次转换过来。代码如下：