Easy

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。你需要执行以下操作 恰好 k 次，以使你的分数最大：

  • 从 nums 中选择一个元素 m。
  • 将选中的元素 m 从数组中删除。
  • 将新元素 m + 1 添加到数组中。
  • 将 m 加到你的分数中。

返回在执行操作恰好 k 次后，你能够获得的最大分数。

示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：18
解释：我们需要从 nums 中恰好选择 3 个元素来最大化和。
第一次迭代，我们选择 5。然后和是 5，nums = [1,2,3,4,6]
第二次迭代，我们选择 6。然后和是 5 + 6，nums = [1,2,3,4,7]  
第三次迭代，我们选择 7。然后和是 5 + 6 + 7 = 18，nums = [1,2,3,4,8]
所以我们将返回 18。
可以证明，18 是我们能够获得的最大答案。

示例 2：

输入：nums = [5,5,5], k = 2
输出：11
解释：我们需要从 nums 中恰好选择 2 个元素来最大化和。
第一次迭代，我们选择 5。然后和是 5，nums = [5,5,6]
第二次迭代，我们选择 6。然后和是 5 + 6 = 11，nums = [5,5,7]
所以我们将返回 11。
可以证明，11 是我们能够获得的最大答案。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

解题思路

这是一道典型的贪心算法题目。关键在于理解每次操作的本质：选择一个元素加入分数，然后将该元素加1后放回数组。

核心思路： 为了最大化总分数，我们应该始终选择数组中的最大元素。因为每次操作后，被选择的元素会加1，所以最优策略就是不断选择当前数组中的最大值。

数学推导： 假设数组的最大值是 max_val，那么进行 k 次操作后，我们选择的元素依次是：

  • 第1次：max_val
  • 第2次：max_val + 1
  • 第3次：max_val + 2
  • …
  • 第k次：max_val + (k-1)

总和就是：max_val + (max_val+1) + ... + (max_val+k-1) = k*max_val + 0+1+2+...+(k-1) = k*max_val + k*(k-1)/2

实现方案：

  1. 模拟法：直接按照题意模拟，每次找最大值，选择后加1放回，重复k次
  2. 数学公式法（推荐）：直接找到最大值，使用上述公式一次计算结果

数学公式法时间复杂度更优，是最佳解法。

代码实现

class Solution {
public:
    int maximizeSum(vector<int>& nums, int k) {
        int maxVal = *max_element(nums.begin(), nums.end());
        return k * maxVal + k * (k - 1) / 2;
    }
};

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        max_val = max(nums)
        return k * max_val + k * (k - 1) // 2

public class Solution {
    public int MaximizeSum(int[] nums, int k) {
        int maxVal = nums.Max();
        return k * maxVal + k * (k - 1) / 2;
    }
}

var maximizeSum = function(nums, k) {
    const maxVal = Math.max(...nums);
    return k * maxVal + k * (k - 1) / 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历数组找到最大值，其中 n 是数组长度
空间复杂度O(1)只使用常数级别的额外空间