1046. 最后一块石头的重量

🟢   🔖  数组 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1]

Output: 1

Explanation:

We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,

we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,

we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,

we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]

Output: 1

Constraints:

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

题目大意

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

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

提示：

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

解题思路

1. 数据结构选择：

   • 由于每次都需要找出最重的两块石头，可以使用大顶堆（优先队列）来存储石头重量。
   • 堆可以快速取出最大值，并支持动态插入操作，适合处理这种需要频繁找最大值的问题。

2. 模拟粉碎过程：

   • 每次从堆中取出最重的两块石头 x 和 y（假设 x <= y）。
   • 如果 x == y，两块石头完全粉碎，不再放回堆中。
   • 如果 x < y，将剩余重量 y - x 插回堆中。
   • 重复上述过程，直到堆中剩下 0 或 1 块石头。

3. 处理特殊情况：

   • 如果最后堆为空，返回 0。
   • 如果最后堆中剩下一块石头，直接返回其重量。

复杂度分析

• 时间复杂度：O(n log n)
  • 堆的初始化的时间复杂度为 O(n)
  • 每次循环中有两个操作（取出两块石头和插入一块石头），每个操作的时间复杂度为 O(log n)。
  • 总共有 n - 1 轮操作，因此循环部分的总时间复杂度为 O(n log n)。
• 空间复杂度：O(n)
  • 堆存储的主要开销为 O(n)
  • 递归栈的开销为 O(log n)
  • 因此，总空间复杂度为：O(n)。

代码

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
	let heap = new MaxHeap(stones);
	while (heap.size() > 1) {
		// 取出最重的两块石头
		const max = heap.pop(); // 最大
		const second = heap.pop(); // 次大
		const diff = max - second;
		if (diff) {
			// 剩余的重量插回堆中
			heap.insert(diff);
		}
	}
	// 返回最后剩下的石头重量，或者 0（如果没有石头）
	return heap.size() ? heap.toArray()[0] : 0;
};

class MaxHeap {
	constructor(arr = []) {
		this.heap = arr;
		for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
			this.heapifyDown(i);
		}
	}

	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	toArray() {
		return this.heap;
	}
	size() {
		return this.heap.length;
	}
	heapifyDown(i) {
		const left = i * 2 + 1;
		const right = i * 2 + 2;
		let max = i;
		if (left < this.heap.length && this.heap[max] < this.heap[left]) {
			max = left;
		}
		if (right < this.heap.length && this.heap[max] < this.heap[right]) {
			max = right;
		}
		if (max !== i) {
			[this.heap[max], this.heap[i]] = [this.heap[i], this.heap[max]];
			this.heapifyDown(max);
		}
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[parent] < this.heap[i]) {
				[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
				i = parent;
			} else {
				break;
			}
		}
	}
}