2558. 从数量最多的堆取走礼物

🟢 🔖 数组 模拟 堆（优先队列） 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

Choose the pile with the maximum number of gifts.
If there is more than one pile with the maximum number of gifts, choose any.
Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining afterk seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation:
The gifts are taken in the following way:
In the first second, the last pile is chosen and 10 gifts are left behind.
Then the second pile is chosen and 8 gifts are left behind.
After that the first pile is chosen and 5 gifts are left behind.
Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation:
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile.
That is, you can't take any pile with you.
So, the total gifts remaining are 4.

Constraints:

1 <= gifts.length <= 10^3
1 <= gifts[i] <= 10^9
1 <= k <= 10^3

题目大意

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

选择礼物数量最多的那一堆。
如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。

返回在 k 秒后剩下的礼物数量。

示例 1：

输入： gifts = [25,64,9,4,100], k = 4
输出： 29
解释：
按下述方式取走礼物：
在第一秒，选中最后一堆，剩下 10 个礼物。
接着第二秒选中第二堆礼物，剩下 8 个礼物。
然后选中第一堆礼物，剩下 5 个礼物。
最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。

示例 2：

输入： gifts = [1,1,1,1], k = 4
输出： 4
解释：
在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。
也就是说，你无法获取任一堆中的礼物。
所以，剩下礼物的总数量是 4 。

提示：

1 <= gifts.length <= 10^3
1 <= gifts[i] <= 10^9
1 <= k <= 10^3

解题思路

使用最大堆存储礼物堆数量
- 初始时将所有礼物堆数量插入最大堆，最大堆的特点是可以快速获取当前最大值，非常适合本题。
重复操作 k 次
- 每次从堆中取出当前礼物数量最多的一堆（即堆顶元素）。
- 将其替换为平方根后的值（向下取整）。
- 重新插入堆中。
计算剩余礼物总数
- k 次操作完成后，堆中存储的是所有礼物堆剩余的数量。
- 遍历堆计算总和，返回结果。

复杂度分析

时间复杂度：O(n + k log n)
- 初始构建最大堆需要 O(n)；
- 执行 k 次取礼物操作，每次插入和删除各 O(log n)，总耗时为 O(k log n)；
- 计算堆中元素总和耗时 O(n)；
- 总时间复杂度为 O(n + k log n)。
空间复杂度：O(n)，最大堆存储 n 个元素。

代码

/**
 * @param {number[]} gifts
 * @param {number} k
 * @return {number}
 */
var pickGifts = function (gifts, k) {
	// 初始化最大堆
	let maxHeap = new MaxHeap(gifts);

	// 执行 k 次操作
	for (let i = 0; i < k; i++) {
		const maxGift = maxHeap.pop(); // 取出最大值
		maxHeap.insert(Math.floor(Math.sqrt(maxGift))); // 替换为平方根后重新插入
	}

	// 计算剩余礼物总数
	return maxHeap.sum();
};

// 最大堆实现
class MaxHeap {
	constructor(arr = []) {
		this.heap = arr;
		for (let i = Math.floor(this.heap.length / 2) - 1; 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 > 0) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}

	size() {
		return this.heap.length;
	}

	sum() {
		return this.heap.reduce((acc, cur) => acc + cur, 0);
	}

	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let max = i;
		if (left < this.heap.length && this.heap[left] > this.heap[max]) {
			max = left;
		}
		if (right < this.heap.length && this.heap[right] > this.heap[max]) {
			max = right;
		}
		if (max !== i) {
			[this.heap[i], this.heap[max]] = [this.heap[max], this.heap[i]];
			this.heapifyDown(max);
		}
	}

	heapifyUp(i) {
		while (i) {
			const parent = Math.floor((i - 1) / 2);
			if (this.heap[i] > this.heap[parent]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}

2558. 从数量最多的堆取走礼物

# 2558. 从数量最多的堆取走礼物

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2558. 从数量最多的堆取走礼物

题目

题目大意

解题思路

复杂度分析

代码

相关题目