What is the main strategy to maximize score in Maximal Score After Applying K Operations?

Always select the current maximum element for each operation using a max-heap and update it with ceil division to maintain the greedy invariant.

Why is a heap necessary for this problem?

A heap allows efficient retrieval and update of the maximum element in O(log n) time per operation, which is critical for large k and n.

Can we use a simple sort and array for selection?

Sorting each time is inefficient because it takes O(n log n) per operation, while a max-heap maintains the greedy selection in O(log n).

How does the ceil operation affect subsequent choices?

It reduces the chosen element for future operations, ensuring that greedy selection always considers the updated values to maintain correctness.

What are common mistakes when implementing this problem?

Not pushing the updated value back into the heap, miscalculating ceil division, or ignoring the heap structure for efficient max retrieval.

#2530

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的起始分数为 0 。在一步操作中：选出一个满足 0 的下标 i ，将你的分数增加 nums[i] ，并且将 nums[i] 替换为 ceil(nums[i] / 3) 。返回在恰好执行 k 次操作后，你可能获…

数组贪心堆（优先队列）

题目描述

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

在一步操作中：

选出一个满足 0 <= i < nums.length 的下标 i ，
将你的分数增加 nums[i] ，并且
将 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⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：优先队列（大根堆）

要使得分数最大化，我们需要在每一步操作中，选择元素值最大的元素进行操作。因此，我们可以使用优先队列（大根堆）来维护当前元素值最大的元素。

每次从优先队列中取出元素值最大的元素 $v$ ，将答案加上 $v$ ，并将 $v$ 替换为 $\lceil \frac{v}{3} \rceil$ ，加入优先队列。重复 $k$ 次后，将答案返回即可。

时间复杂度 $O(n + k \times \log n)$ ，空间复杂度 $O(n)$ 或 $O(1)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        h = [-v for v in nums]
        heapify(h)
        ans = 0
        for _ in range(k):
            v = -heappop(h)
            ans += v
            heappush(h, -(ceil(v / 3)))
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(k log n + n log n) due to heap operations and initial heap construction. Space complexity is O(n) for storing the heap elements.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Ask about choosing a data structure to efficiently retrieve the largest element repeatedly.
question_mark
Discuss the greedy invariant: always selecting the current maximum ensures optimal score.
question_mark
Probe how ceil division affects subsequent operations and heap updates.

warning

常见陷阱

外企场景

error
Forgetting to push the updated value back into the heap after each operation.
error
Incorrectly computing ceil division which can reduce the total score.
error
Not handling large k efficiently, leading to timeouts without heap optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the division factor from 3 to any integer greater than 1.
arrow_right_alt
Use a min-heap to find the minimal score instead of maximal by adjusting the greedy choice.
arrow_right_alt
Allow choosing multiple elements in one operation and summing them before applying ceil division.

help

常见问题

外企场景

继续练习

#2542 最大子序列的分数 #2551 将珠子放入背包中 #2497 图中最大星和