学习记录：js算法（六十四）：最后一块石头的重量

最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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]，这就是最后剩下那块石头的重量。

思路一

var lastStoneWeight = function(stones) {while (stones.length > 1) {stones.sort((a, b) => b - a); // 降序排序let y = stones.shift(); // 取出最大值let x = stones.shift(); // 取出第二大的值if (y !== x) {stones.push(y - x); // 如果不相等，将差值放回数组}}return stones.length ? stones[0] : 0; // 返回最后一个元素或0
};

讲解
解题思路是通过持续找出并处理数组中两个最大的元素，直到数组中只剩下一个元素或没有元素为止

1. 循环处理:
   ○ 创建一个循环，只要stones数组中元素的个数大于1，就进入循环。
   ○ 每次循环的目的是找出并处理两个最大的石头。
2. 排序:
   ○ 在循环内，首先对stones数组进行排序，使用降序排序，即较大的元素排在前面。这样做的目的是确保数组的第一个元素是最大的，第二个元素是次大的。
3. 取出最大值:
   ○ 使用 shift() 方法从排序后的 stones 数组中依次取出第一个和第二个元素，这两个元素分别是当前数组中最大的和次大的石头的重量。
4. 粉碎石头:
   ○ 检查取出的两个元素是否相等。如果不相等，根据题目规则，较大的石头将减去较小石头的重量，得到新的石头重量。
   ○ 如果两个石头的重量相等，它们都将被完全粉碎，不产生新的石头。
5. 更新数组:
   ○ 如果产生了新的石头重量（即两个石头的重量不相等），将这个新的石头重量添加回stones数组中。
   ○ 注意，由于我们在每次循环开始时都会对数组进行排序，所以在添加新石头后，数组的状态将被用于下一次循环的排序。
6. 终止条件:
   ○ 当stones数组中只剩下不到两个元素时，循环结束。这意味着要么数组为空，要么只包含一个元素。
7. 返回结果:
   ○ 最后，检查stones数组的长度。如果数组长度为0，返回0，表示没有石头剩下。如果数组长度为1，返回数组中唯一的元素，即最后剩下的石头的重量。

思路二

var lastStoneWeight = function(stones) {// 创建一个最大堆const maxHeap = new MaxHeap();// 将所有石头的重量插入堆中stones.forEach(stone => maxHeap.insert(stone));// 只要堆中还有至少两块石头while (maxHeap.size() > 1) {// 从堆中取出两块最大的石头const first = maxHeap.extractMax();const second = maxHeap.extractMax();// 根据题目规则处理石头if (first !== second) {// 将粉碎后的新石头重新插入堆中maxHeap.insert(first - second);}}// 返回堆中剩下的石头的重量，如果没有石头则返回0return maxHeap.isEmpty() ? 0 : maxHeap.extractMax();
};// MaxHeap类定义
class MaxHeap {constructor() {this.heap = [];}insert(value) {this.heap.push(value);this.bubbleUp();}extractMax() {const max = this.heap[0];const end = this.heap.pop();if (this.heap.length > 0) {this.heap[0] = end;this.sinkDown();}return max;}bubbleUp() {let idx = this.heap.length - 1;const element = this.heap[idx];while (idx > 0) {let parentIdx = Math.floor((idx - 1) / 2);let parent = this.heap[parentIdx];if (element <= parent) break;this.heap[idx] = parent;this.heap[parentIdx] = element;idx = parentIdx;}}sinkDown() {let idx = 0;const length = this.heap.length;const element = this.heap[0];while (true) {let leftChildIdx = 2 * idx + 1;let rightChildIdx = 2 * idx + 2;let leftChild, rightChild;let swap = null;if (leftChildIdx < length) {leftChild = this.heap[leftChildIdx];if (leftChild > element) {swap = leftChildIdx;}}if (rightChildIdx < length) {rightChild = this.heap[rightChildIdx];if ((swap === null && rightChild > element) ||(swap !== null && rightChild > leftChild)) {swap = rightChildIdx;}}if (swap === null) break;this.heap[idx] = this.heap[swap];this.heap[swap] = element;idx = swap;}}size() {return this.heap.length;}isEmpty() {return this.heap.length === 0;}
};

讲解
利用最大堆（MaxHeap）数据结构来高效地找到并处理数组中的最大元素

1. 创建最大堆：
   ○ 定义一个MaxHeap类，用于创建和管理最大堆。最大堆的性质是每个父节点的值都不小于其子节点的值，这样堆的根节点始终是堆中最大的元素。
2. 插入石头重量：
   ○ 使用forEach循环，将stones数组中的所有石头重量插入到最大堆中。插入时，调用insert方法，该方法将元素添加到堆的末尾，并通过bubbleUp方法保持堆的性质。
3. 处理石头：
   ○ 当堆中元素个数大于1时，进入循环。
   ○ 通过extractMax方法从堆中移除并返回最大的石头重量，此操作会保持堆的性质。
   ○ 重复extractMax，移除并返回堆中当前最大的石头重量，这是第二次最大的石头。
   ○ 如果两次移除的石头重量不相等，计算差值（较大石头减去较小石头），并将这个差值重新插入堆中。
4. 返回结果：
   ○ 循环结束后，堆中最多只剩下一个元素，即最后一块石头的重量。如果堆为空，说明所有石头都已完全粉碎，返回0；否则返回堆顶元素的值。