LeetCode 题解工作台
受标签影响的最大值
以两个整数数组 values 和 labels 给定 n 个项的值和标签，并且给出两个整数 numWanted 和 useLimit 。 你的任务是从这些项中找到一个值的和 最大 的子集使得： 项的数量 最多 为 numWanted 。 相同标签的项的数量 最多 为 useLimit 。 返回最大的…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
根据题目描述，我们需要从 个元素的集合中选出一个子集，子集元素个数不超过 ，且子集中最多有相同标签的 项，使得子集的值之和最大。因此，我们应该贪心地选择集合中值较大的元素，同时记录每个标签出现的次数，当某个标签出现的次数达到 时，我们就不能再选择该标签对应的元素了。 具体地，我们先将集合中的元素按照值从大到小进行排序，然后从前向后遍历排序后的元素。在遍历的过程中，我们使用一个哈希表 记录每…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
以两个整数数组 values 和 labels 给定 n 个项的值和标签，并且给出两个整数 numWanted 和 useLimit 。
你的任务是从这些项中找到一个值的和 最大 的子集使得：
- 项的数量 最多 为
numWanted。 - 相同标签的项的数量 最多 为
useLimit。
返回最大的和。
示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9
解释：
选择的子集是第一个、第三个和第五个项，其值之和为 5 + 3 + 1。
示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12
解释：
选择的子集是第一个、第二个和第三个项，其值之和为 5 + 4 + 3。
示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16
解释：
选择的子集是第一个和第四个项，其值之和为 9 + 7。
提示：
n == values.length == labels.length1 <= n <= 2 * 1040 <= values[i], labels[i] <= 2 * 1041 <= numWanted, useLimit <= n
解题思路
方法一：贪心 + 排序 + 哈希表
根据题目描述，我们需要从 个元素的集合中选出一个子集，子集元素个数不超过 ，且子集中最多有相同标签的 项，使得子集的值之和最大。因此，我们应该贪心地选择集合中值较大的元素，同时记录每个标签出现的次数，当某个标签出现的次数达到 时，我们就不能再选择该标签对应的元素了。
具体地，我们先将集合中的元素按照值从大到小进行排序，然后从前向后遍历排序后的元素。在遍历的过程中，我们使用一个哈希表 记录每个标签出现的次数，如果某个标签出现的次数达到了 ，那么我们就跳过该元素，否则我们就将该元素的值加到最终的答案中，并将该标签出现的次数加 。同时，我们用一个变量 记录当前子集中的元素个数，当 达到 时，我们就可以结束遍历了。
遍历结束后，我们就得到了最大的分数。
时间复杂度 ，空间复杂度 。其中 是集合中的元素个数。
class Solution:
def largestValsFromLabels(
self, values: List[int], labels: List[int], numWanted: int, useLimit: int
) -> int:
ans = num = 0
cnt = Counter()
for v, l in sorted(zip(values, labels), reverse=True):
if cnt[l] < useLimit:
cnt[l] += 1
num += 1
ans += v
if num == numWanted:
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may emphasize handling the label use limit efficiently and checking edge cases where multiple items share the same label.
- question_mark
Expect questions on whether your greedy strategy guarantees the optimal solution and why sorting is necessary for this pattern.
- question_mark
They may probe for time and space optimization, especially how the hash map prevents scanning the array repeatedly for label counts.
常见陷阱
外企场景- error
Failing to sort the items by value first can lead to suboptimal selection and incorrect maximum sum.
- error
Ignoring the useLimit per label, which may exceed allowed selections and produce invalid answers.
- error
Stopping iteration too early or not checking numWanted accurately, leading to incomplete subsets or unused slots.
进阶变体
外企场景- arrow_right_alt
Allowing items to be selected multiple times per label, which shifts the problem from greedy selection to dynamic programming.
- arrow_right_alt
Adding negative values or zero-value items, requiring careful handling to avoid decreasing the sum.
- arrow_right_alt
Restricting the total number of unique labels instead of individual useLimit, which changes the hash tracking logic.