TNotes.leetcode

Appearance

1046. 最后一块石头的重量【简单】

1046. 最后一块石头的重量【简单】 ​

1. 📝 题目描述 ​

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

txt
输入：[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 <= 30
  • 1 <= stones[i] <= 1000

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  // 使用最大堆来模拟过程
  while (stones.length > 1) {
    // 排序以获取最大的两个石头
    stones.sort((a, b) => b - a)

    const first = stones[0]
    const second = stones[1]

    // 移除前两个元素
    stones = stones.slice(2)

    // 如果两个石头重量不同，将差值放回数组
    if (first !== second) {
      stones.push(first - second)
    }
  }

  // 返回剩余的石头重量，如果没有石头则返回0
  return stones.length === 0 ? 0 : stones[0]
}
  • 时间复杂度：O(n2log⁡n)，其中 n 为石头数量，合并过程中需执行多次排序
  • 空间复杂度：O(n)，取决于排序算法的空间开销及数组切分操作

算法思路：

  • 不断对剩余石头进行降序排序，锁定当前最重的两块
  • 按照规则粉碎两块石头，若重量不等则将其差值重新存入数组
  • 循环执行直至剩余石头少于两块，返回最后剩下的石头重量或 0

Discussions