⚡Flashcard Drill➔
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

  1. Each operation takes the current largest value and shrinks it, so the largest value should always be chosen greedily.
  2. A max-heap gives the current maximum in O(log n) per operation.
  3. After taking a value v, push ceil(v / 3) = (v + 2) // 3 back.
  4. 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 // 3 instead 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 k operations must be performed, so all k pops are mandatory.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems