幸福值最大化的选择方案
难度:
标签:
题目描述
You are given an array happiness of length n, and a positive integer k.
There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns.
In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.
Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.
Example 1:
Input: happiness = [1,2,3], k = 2 Output: 4 Explanation: We can pick 2 children in the following way: - Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1]. - Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0. The sum of the happiness values of the selected children is 3 + 1 = 4.
Example 2:
Input: happiness = [1,1,1,1], k = 2 Output: 1 Explanation: We can pick 2 children in the following way: - Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0]. - Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0]. The sum of the happiness values of the selected children is 1 + 0 = 1.
Example 3:
Input: happiness = [2,3,4,5], k = 1 Output: 5 Explanation: We can pick 1 child in the following way: - Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3]. The sum of the happiness values of the selected children is 5.
Constraints:
1 <= n == happiness.length <= 2 * 1051 <= happiness[i] <= 1081 <= k <= n
代码结果
运行时间: 144 ms, 内存: 39.7 MB
/* 思路：
1. 使用Java Stream对幸福值数组进行排序。
2. 使用stream的限制功能选取前k个最大的幸福值。
3. 将选中的幸福值求和作为结果。
*/
import java.util.Arrays;
public class Solution {
public int maxHappiness(int[] happiness, int k) {
// 使用Stream排序并选取前k个最大的幸福值
return Arrays.stream(happiness)
.sorted()
.skip(happiness.length - k)
.sum();
}
}解释
方法:
首先，题解中对happiness数组进行了降序排序，这样可以直接从最大的幸福值开始选择。接下来，会检查第k个元素是否大于等于k，如果是，直接计算前k个元素的和减去一个特定的序列和（0到k-1的和），这是因为每次选择都会使得未选择的元素幸福值减1。如果第k个元素小于k，那么需要寻找一个最大的t（t<=k），使得每个happiness[i]都至少为t，此时计算前t个元素的和减去序列和。这种方法确保了在每轮减少幸福值的情况下，能够获得最大的幸福值总和。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在决定选择孩子的数量t时，题解中将t初始化为0然后逐个检查happiness[i]是否大于等于t？这种方法如何确保达到最优解？
▷🦆
题解中提到如果happiness[k-1] >= k则可以直接计算前k个元素的和减去序列和，这种情况下为什么不需要再考虑后续的幸福值可能减少的问题？
▷🦆
在什么情况下会触发'happiness[k-1] < k'的条件，此时如何确定最大的t值以确保选取的孩子数量是最优的？
▷