2530. 执行 K 次操作后的最大分数

🟠   🔖  贪心 数组 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation :

1. choose an index i such that 0 <= i < nums.length,
2. increase your score by nums[i], and
3. replace nums[i] with ceil(nums[i] / 3).

Return the maximum possiblescore you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

Example 1:

Input: nums = [10,10,10,10,10], k = 5

Output: 50

Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.

Example 2:

Input: nums = [1,10,3,3,3], k = 3

Output: 17

Explanation: You can do the following operations:

Operation 1: Select i = 1, so nums becomes [1,4 ,3,3,3]. Your score increases by 10.

Operation 2: Select i = 1, so nums becomes [1,2 ,3,3,3]. Your score increases by 4.

Operation 3: Select i = 2, so nums becomes [1,1,1 ,3,3]. Your score increases by 3.

The final score is 10 + 4 + 3 = 17.

Constraints:

• 1 <= nums.length, k <= 10^5
• 1 <= nums[i] <= 10^9

题目大意

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

1. 选出一个满足 0 <= i < nums.length 的下标 i ，
2. 将你的 分数 增加 nums[i] ，并且
3. 将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

示例 1：

输入： nums = [10,10,10,10,10], k = 5

输出： 50

解释： 对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2：

输入： nums = [1,10,3,3,3], k = 3

输出： 17

解释： 可以执行下述操作：

第 1 步操作：选中 i = 1 ，nums 变为 [1,4 ,3,3,3] 。分数增加 10 。

第 2 步操作：选中 i = 1 ，nums 变为 [1,2 ,3,3,3] 。分数增加 4 。

第 3 步操作：选中 i = 2 ，nums 变为 [1,2,1 ,3,3] 。分数增加 3 。

最后分数是 10 + 4 + 3 = 17 。

提示：

• 1 <= nums.length, k <= 10^5
• 1 <= nums[i] <= 10^9

解题思路

解决问题的最佳方法是使用 大顶堆（Max Heap），因为它能够高效地找到和弹出当前数组中的最大值。

1. 初始化大顶堆：首先将所有 nums 中的元素加入大顶堆，这样每次都可以轻松地找到当前最大的元素。

2. 执行操作：

   • 在 k 次操作中，每次从堆中弹出最大值，将其加入总分。
   • 然后，将该最大值替换为它除以 3 的向上取整值，继续放回堆中。

3. 返回结果：最终，所有从堆中弹出的元素会被累加成总分，即为最后的结果。

复杂度分析

• 时间复杂度：O(n + k log n)
  • 初始化堆时将 n 个元素加入堆，时间复杂度为 O(n)。
  • 每次操作需要弹出堆顶元素，并将新的元素插入堆。堆操作的时间复杂度是 O(log n)，总共需要执行 k 次操作，因此为 O(k log n)。
  • 因此总时间复杂度为 O(n + k log n)。
• 空间复杂度：O(n)，因为堆中最多同时存储 n 个元素。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxKelements = function (nums, k) {
	let maxHeap = new MaxHeap(),
		res = [];
	for (let i = 0; i < nums.length; i++) {
		maxHeap.push(nums[i]);
	}
	for (let i = 0; i < k; i++) {
		const num = maxHeap.pop();
		res.push(num);
		maxHeap.push(Math.ceil(num / 3));
	}
	return res.reduce((a, b) => a + b, 0);
};
class MaxHeap {
	constructor() {
		this.heap = [];
	}
	push(val) {
		this.heap.push(val);
		this.heapifyUp(this.size() - 1);
	}
	pop() {
		if (this.size() == 0) return null;
		if (this.size() == 1) return this.heap.pop();
		const max = this.heap[0];
		this.heap[0] = this.heap.pop();
		this.heapifyDown(0);
		return max;
	}
	heapifyUp(idx) {
		while (idx) {
			const parent = ((idx - 1) / 2) | 0;
			if (this.heap[idx] > this.heap[parent]) {
				[this.heap[parent], this.heap[idx]] = [
					this.heap[idx],
					this.heap[parent]
				];
				idx = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(idx) {
		const left = idx * 2 + 1,
			right = idx * 2 + 2;
		let min = idx;
		if (left < this.size() && this.heap[left] > this.heap[min]) {
			min = left;
		}
		if (right < this.size() && this.heap[right] > this.heap[min]) {
			min = right;
		}
		if (min !== idx) {
			[this.heap[min], this.heap[idx]] = [this.heap[idx], this.heap[min]];
			this.heapifyDown(min);
		}
	}
	size() {
		return this.heap.length;
	}
}

相关题目

题号	标题	题解	标签	难度
239	滑动窗口最大值	[✓]	队列 数组 滑动窗口 2+
1962	移除石子使总数最小		贪心 数组 堆（优先队列）