NeetCode #820LC-2530MediumGreedy
← Back to All Problems#820 · #2530 · Maximal Score After Applying K Operations(执行 K 次操作后的最大分数)
📌 Problem Statement & Constraints
You are given an integer array
nums and an integer k. In one operation, choose an index i, add nums[i] to your score, then replace nums[i] with ceil(nums[i] / 3). Return the maximum score after exactly k operations. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= k <= 10^5.💡 Core Algorithmic Approaches
- Each operation takes the current largest value and shrinks it, so the largest value should always be chosen greedily.
- A max-heap gives the current maximum in
O(log n)per operation. - After taking a value
v, pushceil(v / 3) = (v + 2) // 3back. - Greedy is optimal because every operation is independent and taking a smaller value now can never enable a larger future gain than taking the current maximum.
💻 Benchmark Python3 Implementation
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
import heapq
heap = [-v for v in nums]
heapq.heapify(heap)
score = 0
for _ in range(k):
v = -heapq.heappop(heap)
score += v
heapq.heappush(heap, -((v + 2) // 3)) # ceiling of v / 3
return score⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + k) log n): heapify is O(n) and each operation is O(log n).
💾 Space Complexity
O(n): the heap.
⚠️ Interview Pitfalls & Follow-ups
- Using
v // 3instead of(v + 2) // 3: integer division truncates, but the operation requires the ceiling. - Sorting once instead of using a heap: a value can be reused many times, and its reduced form re-enters the ordering, so a heap is needed.
- Returning a float from
math.ceil(v / 3): large values lose precision; the integer form is exact. - Stopping early when the heap value becomes small: exactly
koperations must be performed, so allkpops are mandatory.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.