学习记录：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);
    }
  }

  // 返回堆中剩下的石头的重量，如果没有石头则返回0
  return 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；否则返回堆顶元素的值。