Medium

题目描述

给你一个下标从 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^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一道典型的贪心 + 优先队列问题。

核心思路：每次操作都应该选择当前数组中的最大值，因为选择更大的值能获得更多分数。这符合贪心策略的局部最优原则。

算法步骤：

  1. 使用最大堆（优先队列）来维护数组中的所有元素，确保能在 O(log n) 时间内获取最大值
  2. 执行 k 次操作，每次操作：
    • 取出堆顶的最大元素，将其加入总分数
    • 将该元素除以3并向上取整后重新插入堆中
  3. 返回累积的总分数

时间复杂度分析：初始建堆需要 O(n)，每次操作需要 O(log n)，总共 k 次操作，所以整体时间复杂度为 O(n + k log n)。

注意事项：

  • 需要使用 long long 或对应语言的长整型来避免溢出
  • 向上取整可以用 (x + 2) / 3 的技巧来实现，避免浮点运算

这种贪心策略是最优的，因为每一步都选择当前能获得最大收益的元素。

代码实现

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        long long score = 0;
        
        for (int i = 0; i < k; i++) {
            int maxVal = pq.top();
            pq.pop();
            score += maxVal;
            pq.push((maxVal + 2) / 3);
        }
        
        return score;
    }
};

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        import heapq
        # Python的heapq是最小堆，所以用负数来实现最大堆
        heap = [-num for num in nums]
        heapq.heapify(heap)
        
        score = 0
        for _ in range(k):
            max_val = -heapq.heappop(heap)
            score += max_val
            heapq.heappush(heap, -((max_val + 2) // 3))
        
        return score

public class Solution {
    public long MaxKelements(int[] nums, int k) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        
        foreach (int num in nums) {
            pq.Enqueue(num, num);
        }
        
        long score = 0;
        for (int i = 0; i < k; i++) {
            int maxVal = pq.Dequeue();
            score += maxVal;
            int newVal = (maxVal + 2) / 3;
            pq.Enqueue(newVal, newVal);
        }
        
        return score;
    }
}

var maxKelements = function(nums, k) {
    // JavaScript没有内置的优先队列，使用数组模拟
    const heap = [...nums];
    
    // 建立最大堆
    const buildMaxHeap = (arr) => {
        for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    };
    
    const heapify = (arr, i, n) => {
        let largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest !== i) {
            [arr[i], arr[largest]] = [arr[largest], arr[i]];
            heapify(arr, largest, n);
        }
    };
    
    const extractMax = (arr) => {
        const max = arr[0];
        arr[0] = arr[arr.length - 1];
        arr.pop();
        heapify(arr, 0, arr.length);
        return max;
    };
    
    const insertHeap = (arr, val) => {
        arr.push(val);
        let i = arr.length - 1;
        while (i > 0 && arr[Math.floor((i - 1) / 2)] < arr[i]) {
            [arr[i], arr[Math.floor((i - 1) / 2)]] = [arr[Math.floor((i - 1) / 2)], arr[i]];
            i = Math.floor((i - 1) / 2);
        }
    };
    
    buildMaxHeap(heap);
    
    let score = 0;
    for (let i = 0; i < k; i++) {
        const maxVal = extractMax(heap);
        score += maxVal;
        insertHeap(heap, Math.ceil(maxVal / 3));
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k log n)建堆 O(n)，k 次操作每次 O(log n)
空间复杂度O(n)优先队列存储 n 个元素

相关题目