最后一块石头的重量

题目

有一堆石头, 每块石头的重量都是正整数.

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

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

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

提示:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

示例

输入: [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], 这就是最后剩下那块石头的重量.

题解

先从大到小排序, 那么前两个元素一定是 y >= x 的关系, 那就按要求做:

• 如果 y === x, 前两个元素全设为 0
• 如果 y > x, 第一个元素设为 stones[0] - stones[1], 第二个元素设为 0

再从大到小排序, 直到第二个元素也是 0, 说明要么团灭, 要么 stones[0] 养蛊成功, 结束循环, 返回 stones[0] 即可.

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  if (stones.length === 1) return stones[0]
  stones.sort((a, b) => b - a)

  while (stones[1] > 0) {
    if (stones[0] === stones[1]) {
      stones[0] = 0
      stones[1] = 0
    } else {
      stones[0] = stones[0] - stones[1]
      stones[1] = 0
    }

    stones.sort((a, b) => b - a)
  }

  return stones[0]
}