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

2023-05-31 HGNULB 约 10 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1090. 受标签影响的最大值

题意分析

输入是两个等长数组：values[i] 是第 i 个物品的分值，labels[i] 是它所属的类别。我们要从中挑出一个子集，使得子集里的元素个数不超过 numWanted，且同一个 label 被选中的个数不超过 useLimit，目标是让被选中元素的分值之和最大。注意题目只问「最大和是多少」，不要求还原具体选了哪些下标，这一点会直接影响我们能省掉多少状态。

约束里有几个信号值得读出来。第一，只有两条限制，一条是全局的总数上限，一条是按 label 分组的局部上限，两者之间没有耦合，不存在「选了 A 就不能选 B」这种成对冲突，所以不需要搜索或者匹配。第二，values[i] 都是正数，这意味着能多选就多选一定不亏，不存在「选进来反而变小」的情况，选够 numWanted 个才是最优形态（当合法元素足够多时）。第三，数据规模 n 到 2 万级别，$O(n^2)$ 的成对枚举会超时，但 $O(n \log n)$ 完全够用，这就把答案框在了排序这一档复杂度上。

边界方面要留意三种：numWanted 可能大于数组长度，此时能选的其实是全部合法元素，循环自然结束即可，不需要特判；useLimit 可能为 0，此时任何元素都不能选，答案是 0；所有元素可能挤在同一个 label 下，此时最多只能选出 useLimit 个，最终选中数量会小于 numWanted，这不算异常，是正常终止。

解法：排序 + 贪心

核心思路

最朴素的想法是枚举所有子集，检查是否满足两条限制，然后取和最大的那个。子集数量是 $2^n$，n 到 2 万时这条路完全不可行。退一步，能不能做背包？把「已选个数」和「每个 label 已用次数」都塞进状态，状态维度随 label 种类数指数膨胀，同样不现实。瓶颈很清楚：我们在为一个根本不需要全局权衡的问题付出全局搜索的代价。

关键观察是这样的：假设最优解里选中了元素 x，而存在一个没被选中的元素 y，满足 values[y] > values[x] 且 labels[y] == labels[x]，那么把 x 换成 y，两条约束都不受影响（总个数不变，该 label 的使用次数也不变），而总和严格变大——这与「最优」矛盾。这说明在同一个 label 内部，被选中的一定是分值最大的那几个。再进一步，跨 label 之间也成立：若最优解选了 x 没选 y，values[y] > values[x] 且 y 所在 label 还有余额，同样可以交换得到更优解。两条交换论证合起来告诉我们，按分值从大到小依次考察每个元素，只要它所在 label 还没用满就选，这样得到的解不会比任何其他方案差。

于是不变量可以显式写出来：按分值降序扫描到第 i 个元素时，cnt[label] 恰好等于前 i 个元素中被选中且属于该 label 的个数，picked 是已选总数，sum 是这批已选元素的分值和；并且这批已选元素，是「只考虑前 i 个元素」这个子问题的一个最优选择。扫描结束或 picked 达到 numWanted 时，这个不变量就退化成了全局最优解。因为 values 全为正，提前把名额用在更大的元素上永远不会后悔，这正是贪心成立的根基。

解题步骤

第一步是建立下标数组并按分值降序排序。之所以排下标而不是直接排 values，是因为 values[i] 和 labels[i] 是按位置绑定的，一旦直接对 values 排序，两者的对应关系就断了。排下标相当于给「值—标签」这个二元组做了一次整体重排，代价只是一层间接寻址。

第二步是准备三个状态：哈希表 cnt 记录每个 label 已经用掉几个名额，picked 记录已选总数，sum 累加答案。用哈希表而不是定长数组，是因为 label 的取值范围题目没有承诺很小，哈希表对稀疏的 label 空间更稳妥。

第三步是主循环，按排好的顺序逐个考察。进入循环体先检查 picked == numWanted，达到上限立刻 break——这条检查必须放在最前面，因为一旦名额用完，后面的元素无论 label 是否有余额都不该再选。接着取出该元素的 label，读出已用次数 used，若 used == useLimit 就 continue 跳过这个元素，注意是跳过而不是终止，因为别的 label 可能还有余额。

第四步是选中动作，三件事必须同时做：cnt 里该 label 加一、sum 累加分值、picked 加一。三者是同一个不变量的三个分量，漏掉任何一个都会让状态不自洽。循环自然结束（元素扫完）或被 break 打断后，sum 就是答案，不需要额外收尾。

以 values = [5,4,3,2,1]、labels = [1,1,2,2,3]、numWanted = 3、useLimit = 1 走一遍。排序后下标序列是 [0,1,2,3,4]，对应分值 5、4、3、2、1。第一轮取下标 0，picked=0 未满，label 为 1，used=0 小于 1，于是选中：cnt[1]=1、sum=5、picked=1。第二轮取下标 1，label 同样是 1，used=1 已等于 useLimit，continue 跳过——这里体现了 useLimit 的作用，尽管 4 是剩余最大值也不能要。第三轮取下标 2，label 为 2，used=0，选中：cnt[2]=1、sum=8、picked=2。第四轮取下标 3，label 仍是 2 且已用满，跳过。第五轮取下标 4，label 为 3，used=0，选中：sum=9、picked=3。第六轮循环不存在，扫描结束，返回 9。若把 numWanted 改成 2，则在第五轮开头 picked 已等于 2，直接 break，返回 8——可以看到两条约束分别在不同位置生效，互不干扰。

代码实现

class Solution {
    // 对每个标签维护已选数量，超过 useLimit 则跳过。
    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;
    }
}

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
    // 对每个标签维护已选数量，超过 useLimit 则跳过。
    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)$，其中 n 表示元素数量。建立下标数组是 $O(n)$，比较排序占 $O(n \log n)$ 并且是全流程的主导项，主循环每个元素只被访问一次、哈希表读写均摊 $O(1)$，合计仍是 $O(n \log n)$。

空间复杂度：$O(n)$，下标数组占 $O(n)$，哈希表最坏情况下每个元素一个不同 label 也是 $O(n)$，排序本身的辅助空间不超过这一量级。

关键点总结

贪心的正确性靠交换论证站住：任取一个最优解，若存在「未选的更大元素且其 label 仍有余额」，就能无损替换出更优解，矛盾说明降序取即最优。面试时把这段推导讲出来，比背结论更能拿分。

两条约束的检查位置不能混：全局名额 numWanted 用 break 终止整个流程，label 名额 useLimit 用 continue 跳过单个元素。区分「终止」与「跳过」是这类多重限额题的通用套路。

需要按某个字段排序、又要保留与另一数组的对应关系时，排下标是标准做法，比构造结构体数组更轻，也避免了拆包重组的心智负担。

「元素全为正」是贪心能一路取到底的前提。面试官常追问「如果 values 允许为负呢」，答案是选负数只会让和变小，此时应在选中前加一条 values[id] > 0 的判断，其余逻辑不变。

用哈希表而非定长数组承载分组计数，是因为 label 的值域未被承诺有界。当面试官补充「label 一定在 0 到 n-1 之间」时可以换成数组，常数更小。

这道题的模板可迁移到一切「总量上限 + 分组上限 + 最大化收益」的场景，例如按类目限购的选品、按团队限额的人员挑选，识别出这个形状就能直接套排序加计数。

易错点总结

错误写法：直接 Arrays.sort(values) 后再按下标读 labels。用例 values = [5,4,3,2,1]、labels = [1,1,2,2,3] → 排序只动了 values，labels 原地不动，值与标签的绑定关系被打散，选中的标签完全对不上，答案错成 12。

错误写法：把 if (picked == numWanted) break; 写在选中动作之后。用例 numWanted = 1、values = [5,4]、labels = [1,2] → 选完 5 后不立即退出，下一轮还会把 4 也选进来，返回 9 而非 5。

错误写法：label 用满时写 break 而不是 continue。用例 values = [5,4,3]、labels = [1,1,2]、numWanted = 2、useLimit = 1 → 第二轮遇到用满的 label 1 就整体终止，永远够不到 label 2 的元素 3，返回 5 而非 8。

错误写法：选中时只累加 sum 忘了 cnt.put(label, used + 1)。用例 values = [5,4,3]、labels = [1,1,1]、numWanted = 3、useLimit = 1 → 计数永远是 0，三个元素全被选中，返回 12 而非 5。

错误写法：选中时忘记 picked++。用例 numWanted = 1、values = [5,4]、labels = [1,2] → 全局名额永远不会达到上限，两个都被选，返回 9 而非 5。

错误写法：把用满判断写成 if (used > useLimit) continue;。用例 values = [5,4]、labels = [1,1]、useLimit = 1 → used == 1 时判断为假，第二个元素被放行，该 label 用了 2 次，返回 9 而非 5。

错误写法：useLimit = 0 时没意识到 used == useLimit 在首轮就成立，反而额外写了 if (useLimit == 0) return sum; 之后又忘了初始化 sum。用例 useLimit = 0 → 返回未定义的脏值，其实原逻辑天然处理这个边界，无需特判。

错误写法：Java 里用 int[] 配合 Arrays.sort 想做自定义比较。用例任意输入 → Arrays.sort(int[], Comparator) 根本不存在，编译不通过，必须用装箱的 Integer[] 才能传比较器。

错误写法：Go 里写成 sort.Slice(idx, func(i, j int) bool { return values[i] > values[j] })。用例 values = [1,5] → 比较器拿 i、j 当成了原数组下标而非 idx 中的位置，排序结果是乱的，与预期顺序不符。

错误写法：认为答案一定要选满 numWanted 个，于是在选不够时补上重复元素。用例 values = [5,4]、labels = [1,1]、numWanted = 3、useLimit = 1 → 只能选出 1 个，硬凑会重复计入分值，返回 15 而非 5。

相似题目

题目	难度	考察点
2542. 最大子序列的分数	中等	同为「选 K 个最大化收益」，但收益是乘积形式，需排序后配小顶堆
502. IPO	困难	贪心对象随资本变化而动态解锁，用双排序加大顶堆而非一次扫描
621. 任务调度器	中等	同样按类别计数，但求的是最短耗时，靠最高频类别推公式
435. 无重叠区间	中等	贪心排序键是右端点而非权值，交换论证的方向不同
1005. K 次取反后最大化的数组和	简单	名额是「操作次数」而非「选中个数」，负数存在使贪心多一层讨论
347. 前 K 个高频元素	中等	只按计数取前 K，没有分组限额，可用桶排序做到线性
179. 最大数	中等	考点在自定义比较器的传递性证明，而非选择策略
630. 课程表 III	困难	需要「反悔贪心」，选错可以用堆撤回，本题一旦选中不可回退
2462. 雇佣 K 位工人的总代价	中等	候选集合被左右指针限制在滑动区间内，不能一次性全局排序
763. 划分字母区间	中等	同样按 label 分组，但目标是切分位置，靠末次出现下标而非计数