题目描述
思路解析动画文字版
记牢三步:先按值从大到小排;从大往小扫,标签没满就选、满了就跳;选够 numWanted 就停。标签用没用满,靠一张计数表来查。
排序前 · 原始顺序：这是原始的 7 个项,值的顺序是乱的。贪心要从大值开始,所以第一步先把它们按值从大到小排一遍。
排序后 · 值从大到小：排好了,值从 9 到 3 依次往下。对应的标签变成 1、1、1、2、2、3、3。接下来就从最左边最大的 9 开始,一个一个往右考察。
读第 1 项 · 值 9：轮到从左数第 1 个项,它的值是 9,标签是 1。现在已经选了 0 项,和是 0。先去查一下:标签 1 这一组,还能不能再选。
判定 · 标签 1 已选 0 个：标签 1 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 9 可以收进来。
选入 · 第 1 项：把 9 收进答案,和从 0 涨到 9,标签 1 的计数加到 1,已选项数变成 1。还没到 5 个,继续往右看。
读第 2 项 · 值 8：轮到从左数第 2 个项,它的值是 8,标签是 1。现在已经选了 1 项,和是 9。先去查一下:标签 1 这一组,还能不能再选。
判定 · 标签 1 已选 1 个：标签 1 目前选了 1 个,还没到上限 2,1 小于 2 成立,所以这个值 8 可以收进来。
选入 · 第 2 项：把 8 收进答案,和从 9 涨到 17,标签 1 的计数加到 2,已选项数变成 2。还没到 5 个,继续往右看。
读第 3 项 · 值 7：轮到从左数第 3 个项,它的值是 7,标签是 1。现在已经选了 2 项,和是 17。先去查一下:标签 1 这一组,还能不能再选。
判定 · 标签 1 已选 2 个：标签 1 已经选满了 2 个,等于上限 2,2 小于 2 不成立,这个项不能再要了。
跳过 · 第 3 项：所以第 3 项只能放弃,值 7 不计入,和还是 17。注意它被跳过不是因为值小,而是标签 1 的名额用光了。看下一个。
读第 4 项 · 值 6：轮到从左数第 4 个项,它的值是 6,标签是 2。现在已经选了 2 项,和是 17。先去查一下:标签 2 这一组,还能不能再选。
判定 · 标签 2 已选 0 个：标签 2 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 6 可以收进来。
选入 · 第 4 项：把 6 收进答案,和从 17 涨到 23,标签 2 的计数加到 1,已选项数变成 3。还没到 5 个,继续往右看。
读第 5 项 · 值 5：轮到从左数第 5 个项,它的值是 5,标签是 2。现在已经选了 3 项,和是 23。先去查一下:标签 2 这一组,还能不能再选。
判定 · 标签 2 已选 1 个：标签 2 目前选了 1 个,还没到上限 2,1 小于 2 成立,所以这个值 5 可以收进来。
选入 · 第 5 项：把 5 收进答案,和从 23 涨到 28,标签 2 的计数加到 2,已选项数变成 4。还没到 5 个,继续往右看。
读第 6 项 · 值 4：轮到从左数第 6 个项,它的值是 4,标签是 3。现在已经选了 4 项,和是 28。先去查一下:标签 3 这一组,还能不能再选。
判定 · 标签 3 已选 0 个：标签 3 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 4 可以收进来。
选入 · 第 6 项：把 4 收进答案,和变成 32,标签 3 的计数加到 1。这下已选项数到了 5,正好等于上限 numWanted = 5,不能再选了,扫描就此停下。
完成 · 最大和 32：扫到选满 5 项就停了,绿色的就是选中的:9、8、6、5、4,加起来等于 32。被划掉的那个是标签名额满了才跳过的;最右边那个 3 因为提前选够了,根本没轮到考察。最终答案 32。
边界先想清:useLimit 为 0 选不了任何项返回 0、只选 1 个就拿最大、每标签卡 useLimit 个。
面试重点:交换论证证明贪心正确、用哈希表同时卡两条上限、比普通 Top-K 多一层标签分组约束。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(n log n)，n 是项数。排序是 O(n log n),是主导项;之后只扫一遍每项做常数次哈希操作,是 O(n)。合起来 O(n log n)
- 空间：O(n)，排序用的配对数组 O(n) + 标签计数哈希 O(k),k 是不同标签数不超过 n。排序内部 C++ 与 Java 递归栈约 O(log n)、Python 的 Timsort 最坏 O(n),峰值都不超过 O(n)
易错点
面试追问把动画讲成自己的话
追问这个贪心为什么是对的,会不会漏掉更优解?
追问数量上限和标签上限是怎么同时处理的?
追问这题和普通的取前 K 大有什么不同?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
交换字符使得字符串相同
LeetCode 1247 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题