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

给你一个下标从 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 。

解题思路

输入： 一个整数数组 nums, 一个整数 k

输出： 执行 k 次操作后，可能获得的最大分数

方法分析

• 我们可以使用 最大堆（Max Heap） 来降低复杂度。

具体做法

• 每次操作都需要取当前最大值 ⇒ 使用 最大堆（MaxHeap）；
• 将最大值加到分数中；
• 将 ceil(max / 3) 放回堆；
• 重复执行 k 次；
• 返回总分。

代码实现

python

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        # 使用最大堆，Python 的 heapq 是一个最小堆，因此我们存储负值来模拟最大堆
        max_heap = [-num for num in nums]  # 将每个元素取负
        heapq.heapify(max_heap)  # 将列表转化为堆
        
        score = 0  # 初始化分数
        
        for _ in range(k):
            # 从最大堆中取出当前最大值
            max_num = -heapq.heappop(max_heap)  # 取出最大值并转正
            score += max_num  # 增加分数
            
            # 更新值并将其放回堆中
            updated_num = math.ceil(max_num / 3)  # 计算新值
            heapq.heappush(max_heap, -updated_num)  # 将新值取负后放回堆中
        
        return score  # 返回最终分数

javascript

var maxKelements = function(nums, k) {
    const heap = new MaxHeap();

    // 1️⃣ 将所有元素放入最大堆
    for (let num of nums) {
        heap.insert(num);
    }

    let score = 0;

    // 2️⃣ 执行 k 次操作
    for (let i = 0; i < k; i++) {
        const max = heap.pop();         // 取出当前最大值
        score += max;                   // 累加到得分
        const next = Math.ceil(max / 3); // 向上取整后重新入堆
        heap.insert(next);
    }

    // 3️⃣ 返回总得分
    return score;
};

复杂度分析

时间复杂度：O(k log n)

空间复杂度：O(n)

链接

2530 国际版

2530 中文版