跳转至

LeetCode: 1090. 受标签影响的最大值

1、题目描述

我们有一个项的集合,其中第 i 项的值为 values[i],标签为 labels[i]

我们从这些项中选出一个子集 S,这样一来:

  • |S| <= num_wanted
  • 对于任意的标签 L,子集 S 中标签为 L 的项的数目总满足 <= use_limit。

返回子集 S 的最大可能的 和。

示例 1:

输入:values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出:9
解释:选出的子集是第一项,第三项和第五项。

示例 2:

输入:values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出:12
解释:选出的子集是第一项,第二项和第三项。

示例 3:

输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出:16
解释:选出的子集是第一项和第四项。

示例 4:

输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出:24
解释:选出的子集是第一项,第二项和第四项。

提示:

  • 1 <= values.length == labels.length <= 20000
  • 0 <= values[i], labels[i] <= 20000
  • 1 <= num_wanted, use_limit <= values.length

2、解题思路

  • 贪心法
  • 每次都找最大的值,如果当前值对应的标签在允许范围内,更新结果值
from collections import defaultdict


class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
        label_appear = defaultdict(int)
        count = 0
        ans = 0

        for v, l in sorted(zip(values, labels), reverse=True):
            if count == num_wanted:
                break
            if label_appear[l] < use_limit:
                label_appear[l] += 1
                ans += v
                count += 1
        return ans