K 件物品的最大和
难度:
标签:
题目描述
There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.
You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.
The bag initially contains:
numOnesitems with1s written on them.numZeroesitems with0s written on them.numNegOnesitems with-1s written on them.
We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.
Example 1:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
Output: 2
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.
Example 2:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
Output: 3
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.
Constraints:
0 <= numOnes, numZeros, numNegOnes <= 500 <= k <= numOnes + numZeros + numNegOnes
代码结果
运行时间: 19 ms, 内存: 16.0 MB
/*
* 题目思路：
* 要从袋子中选出恰好k件物品，使其标记数字之和最大。
* 我们优先选择标记为1的物品，如果剩余的k还不够，则选择标记为0的物品，
* 最后如果k还需要选择物品，则选择标记为-1的物品。
*/
import java.util.stream.IntStream;
public class MaxSumFromBagStream {
public int getMaxSum(int numOnes, int numZeros, int numNegOnes, int k) {
int[] items = new int[numOnes + numZeros + numNegOnes];
IntStream.range(0, numOnes).forEach(i -> items[i] = 1);
IntStream.range(numOnes, numOnes + numZeros).forEach(i -> items[i] = 0);
IntStream.range(numOnes + numZeros, items.length).forEach(i -> items[i] = -1);
return IntStream.of(items).boxed()
.sorted((a, b) -> Integer.compare(b, a))
.limit(k)
.mapToInt(Integer::intValue)
.sum();
}
public static void main(String[] args) {
MaxSumFromBagStream solution = new MaxSumFromBagStream();
System.out.println(solution.getMaxSum(3, 2, 0, 2)); // 输出: 2
System.out.println(solution.getMaxSum(3, 2, 0, 4)); // 输出: 3
}
}
解释
方法:
题解的核心思路是优先选取对总和贡献最大的物品。首先尽可能多地选择标记为 1 的物品，因为每个这样的物品都能为总和增加 1。当标记为 1 的物品不足以填满 k 时，选择标记为 0 的物品，这些物品不会增加也不会减少总和。如果还需要选择更多物品，最后选择标记为 -1 的物品，尽管这会减少总和。这个策略确保了在给定的物品和限制下，总和达到可能的最大值。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，为什么选择标记为0的物品时，没有对总和`total_sum`进行更新？
▷🦆
如果`k`大于所有物品的总和（`numOnes + numZeros + numNegOnes`），题解中的算法如何处理这种情况？
▷🦆
题解提到尽可能少地选择标记为-1的物品，但如果需要选择的数量`k`非常大，选择-1的物品是否会影响到总和达到最大值的目标？
▷🦆
题解中的算法逻辑是否考虑了所有边界情况，例如当`numOnes`, `numZeros`, 或`numNegOnes`为0时的情况？
▷