LeetCode 1090. 受标签影响的最大值
题目描述
题意分析
第
i项的分值和标签分别是values[i]、labels[i]。选择的总数不能超过numWanted，同一个标签的选取数不能超过useLimit，要求分值总和最大，不要求必须凑满名额。分值都非负，因此只要还有合法名额，多选一项不会让答案变小。标签限制只影响同类中的选取数量，可以先按分值从大到小考虑，再跳过已经用满标签名额的项。
解法：排序 + 贪心
核心思路
[!blue]
对任意一个标签，只需考虑分值最高的
useLimit项：如果方案选了较低分的一项，却没选更高分的同标签项，直接替换后数量限制不变，总分不会减少。因此总有一个最优方案只使用这些候选；该标签不足useLimit项时则全部保留。将所有标签的候选放在一起，每个标签至多已有
useLimit项，所以从中任选子集都满足标签限制。剩下只需取全局分值最大的至多numWanted项；若候选不足，全部取走就是最优解。代码把这两步合为一次降序扫描。
idx保存排序后的原下标，保证每个分值仍能找到对应标签；cnt[label]记录该标签已选数量，picked记录总数量，sum记录总分。遇到未满额标签就选取，遇到已满额标签就跳过；降序保证被选中的正是每个标签最有价值的那些项。
picked达到总上限时，后面的分值都不更大，可以结束；某个标签满额时，其他标签仍可能有可选项，因此只能跳过当前项。相同分值之间任选顺序都不会降低最优总和。
解题步骤
- 排序下标，保持分值与标签配对。
- 标签已满就跳过，否则累计分值与两种计数。
- 达到总数上限或扫描完毕后返回。
代码实现
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
Integer[] idx = new Integer[values.length];
for (int i = 0; i < values.length; i++) {
idx[i] = i;
}
// 按下标排序，保持分值与标签的对应。
Arrays.sort(idx, (a, b) -> values[b] - values[a]);
Map<Integer, Integer> cnt = new HashMap<>();
int picked = 0;
int sum = 0;
for (int id : idx) {
// 总名额用满才结束，单个标签用满只跳过。
if (picked == numWanted) {
break;
}
int label = labels[id];
int used = cnt.getOrDefault(label, 0);
if (used == useLimit) {
continue;
}
// 选中后同时维护标签用量、总分和已选数量。
cnt.put(label, used + 1);
sum += values[id];
picked++;
}
return sum;
}
}
import "sort"
func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
idx := make([]int, len(values))
for i := 0; i < len(values); i++ {
idx[i] = i
}
// 按下标排序，保持分值与标签的对应。
sort.Slice(idx, func(i, j int) bool {
return values[idx[i]] > values[idx[j]]
})
cnt := make(map[int]int)
picked := 0
sum := 0
for _, id := range idx {
// 总名额用满才结束，单个标签用满只跳过。
if picked == numWanted {
break
}
label := labels[id]
used := cnt[label]
if used == useLimit {
continue
}
// 选中后同时维护标签用量、总分和已选数量。
cnt[label] = used + 1
sum += values[id]
picked++
}
return sum
}
复杂度分析
- 时间复杂度：期望 $O(n\log(n+1))$。排序下标需要 $O(n\log(n+1))$，之后扫描一次，每次标签计数查询和更新的期望时间为 $O(1)$。
- 空间复杂度：$O(n)$，下标数组与标签计数。
关键点总结
[!green]
- 全局已满结束全部扫描，单个标签已满只跳过当前项。
- 排序的是下标，不会打散值与标签关系。
易错点总结
[!yellow]
- 只排序 values 会读到不对应的标签。
- 某标签满了就退出，会漏掉后续其他标签。
- 选中时忘记增加任一计数，会超过相应限制。
- 合法候选不足
numWanted时直接返回已有总和，不能为了凑满数量突破某个标签的上限。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 215. 数组中的第K个最大元素 | 中等 | 本题不能直接选全局前k大，还要在贪心扫描时维护每种标签已使用的配额。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！