题目描述
思路解析
一句话答案：LeetCode 1090 受标签影响的最大值：两条上限下让选中值之和最大，按值从大到小排序后贪心地拿，标签没满且总数没到 numWanted 就收、卡住就跳，时间 O(n log n)。
两条上限夹着，怎么把选中的值堆到最大
给两个一样长的数组 values 和 labels，第 i 个项有个值 values[i] 和标签 labels[i]。挑一批项，守两条线：总共最多挑 numWanted 个，同一个标签最多挑 useLimit 个；在这之内让挑中的值加起来最大。题面例子 values=[5,4,3,2,1]、labels=[1,1,2,2,3]、numWanted=3、useLimit=1，答案 9=5+3+1。
光盯着大值往篮子里塞，会撞上哪堵墙
你自然想先把最大的几个抓走。可 values=[5,4,3,2,1] 里最大的 5 和次大的 4 都挂着标签 1，而 useLimit=1 只准标签 1 出一个。真按值一路抢，抢到 4 就得刹住，否则会得到标签 1 拿两个的非法结果、和虚高。拿够 numWanted 就不能再要。排个大小照单全收行不通。
为什么排完序还能边扫边挑，不用回头反悔
办法是把所有项按值从大到小排一遍，再从最大的往下看。看到一个项，先查它的标签还有没有名额：没满就收进来、值加进答案，满了就跳过；总数够了 numWanted 就收手。它成立在于：同一个标签能占的名额有限，就该留给值大的；排序保证先遇到的最大，后面同标签只会更小，跳过不亏。
一个哈希表，同时管住标签和总数两条线
扫描时备一张计数表，也就是一个哈希表，记每个标签选了几个。轮到某个项，设它的标签是 l：只要 cnt[l]＜useLimit 就选它，cnt[l] 加一、num 加一、ans 加上这个值；num 一等于 numWanted 就立刻停。cnt[l] 已等于 useLimit 的项直接略过，它后面同标签的更小值也轮不上。两条上限各查各的：标签看 cnt[l]，总数看 num，互不打架。
拿 [5,4,3,2,1] 按两上限逐个筛出 9
把每项的值与标签配对，按值从大到小排，得到 (5,1)、(4,1)、(3,2)、(2,2)、(1,3)，开头 ans=0、num=0。(5,1)：标签 1 有名额 0＜1，收下，ans=5、num=1、cnt[1]=1。(4,1)：标签 1 满了 1＜1 不成立，跳过。(3,2)：标签 2 有名额 0＜1，收下，ans=8、num=2。(2,2)：标签 2 满了，跳过。(1,3)：标签 3 有名额 0＜1，收下，ans=9、num=3，num 到 numWanted=3，停。最后 ans=9，正是 5+3+1。
排序占大头 O(n log n)，两个方向别栽进去
时间上，把 n 个项排序是 O(n log n)，是主导项；之后扫一遍、每项做几次常数哈希操作是 O(n)，合起来 O(n log n)。空间上，配对数组 O(n)、标签计数表也不超过 O(n)。
排序方向是第一道坎：按值从小到大排的话，先被塞进名额的全是小值，等大值轮到时标签或总数早满了，和只会偏小，所以一定得从大到小。停手条件是第二道：num 到了 numWanted 还不刹车，接着扫要么白算，要么把总数撑破。还有个极端 useLimit=0，谁都开不了张，答案就是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢三步:先按值从大到小排;从大往小扫,标签没满就选、满了就跳;选够 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题