1090. 受标签影响的最大值【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 排序

1. 📝 题目描述

• leetcode

以两个整数数组 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.length
• 1 <= n <= 2 * 10^4
• 0 <= values[i], labels[i] <= 2 * 10^4
• 1 <= numWanted, useLimit <= n

2. 🎯 s.1 - 贪心 + 排序

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} values
 * @param {number[]} labels
 * @param {number} numWanted
 * @param {number} useLimit
 * @return {number}
 */
var largestValsFromLabels = function (values, labels, numWanted, useLimit) {
  const indices = values.map((_, i) => i).sort((a, b) => values[b] - values[a])
  const labelCount = new Map()
  let res = 0,
    count = 0
  for (const i of indices) {
    const label = labels[i]
    const used = labelCount.get(label) || 0
    if (used >= useLimit) continue
    res += values[i]
    labelCount.set(label, used + 1)
    if (++count === numWanted) break
  }
  return res
}

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(n)$，排序和哈希表的开销

算法思路：

• 将所有项按值降序排序
• 贪心选取值最大的项，用哈希表记录每个标签已用次数
• 若某标签已达 useLimit 则跳过，直到选够 numWanted 个项