Medium

题目描述

给定一个长度为 n 的数组 happiness 和一个正整数 k。

有 n 个儿童排成一队，第 i 个儿童的幸福值为 happiness[i]。你需要在 k 轮中从这 n 个儿童中选择 k 个儿童。

在每一轮中，当你选择一个儿童时，所有还没有被选择的儿童的幸福值都会减少 1。注意幸福值不能变成负数，只有当它是正数时才会减少。

通过选择 k 个儿童，返回所选儿童幸福值的最大总和。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：我们可以按以下方式选择 2 个儿童：
- 选择幸福值为 3 的儿童。剩余儿童的幸福值变为 [0,1]。
- 选择幸福值为 1 的儿童。剩余儿童的幸福值变为 [0]。注意幸福值不能小于 0。
所选儿童的幸福值总和为 3 + 1 = 4。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：我们可以按以下方式选择 2 个儿童：
- 选择任意一个幸福值为 1 的儿童。剩余儿童的幸福值变为 [0,0,0]。
- 选择幸福值为 0 的儿童。剩余儿童的幸福值变为 [0,0]。
所选儿童的幸福值总和为 1 + 0 = 1。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：我们可以按以下方式选择 1 个儿童：
- 选择幸福值为 5 的儿童。剩余儿童的幸福值变为 [1,2,3]。
所选儿童的幸福值总和为 5。

约束：

  • 1 <= n == happiness.length <= 2 * 10^5
  • 1 <= happiness[i] <= 10^8
  • 1 <= k <= n

解题思路

这是一道贪心算法题。关键观察在于：每次选择儿童时，所有未被选择的儿童的幸福值都会减少1。

核心思路：

由于所有未被选择的数值都以相同的速率递减，我们应该贪心地选择当前最大的 k 个值。具体来说：

  1. 排序策略：将数组按降序排序，优先选择幸福值最高的儿童
  2. 递减规律：第 i 个被选择的儿童（从0开始计数）在被选择时，其幸福值已经减少了 i 次
  3. 非负约束：如果计算后的幸福值为负数，则贡献0

算法步骤：

  1. 对幸福值数组进行降序排序
  2. 依次选择前 k 个最大值
  3. 对于第 i 个选择（从0开始），其实际贡献为 max(0, happiness[i] - i)
  4. 累加所有贡献值

时间复杂度分析：

  • 排序：O(n log n)
  • 遍历前k个元素：O(k)
  • 总体：O(n log n)

这种贪心策略是最优的，因为我们总是在每一步选择当前可获得的最大收益。

代码实现

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end(), greater<int>());
        
        long long result = 0;
        for (int i = 0; i < k; i++) {
            result += max(0, happiness[i] - i);
        }
        
        return result;
    }
};

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        
        result = 0
        for i in range(k):
            result += max(0, happiness[i] - i)
        
        return result

public class Solution {
    public long MaximumHappinessSum(int[] happiness, int k) {
        Array.Sort(happiness, (a, b) => b.CompareTo(a));
        
        long result = 0;
        for (int i = 0; i < k; i++) {
            result += Math.Max(0, happiness[i] - i);
        }
        
        return result;
    }
}

/**
 * @param {number[]} happiness
 * @param {number} k
 * @return {number}
 */
var maximumHappinessSum = function(happiness, k) {
    happiness.sort((a, b) => b - a);
    
    let result = 0;
    for (let i = 0; i < k; i++) {
        result += Math.max(0, happiness[i] - i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，其中 n 为数组长度
空间复杂度O(1)只使用常数额外空间（不考虑排序的空间开销）

相关题目