受标签影响的最大值 图解题解
这道题到底在问什么
- 输入
- values=[5,4,3,2,1], labels=[1,1,2,2,3], numWanted=3, useLimit=1
- 输出
- 9 = 5 + 3 + 1
- 输入
- 本节演示 numWanted=5, useLimit=2
- 输出
- 32
先想最直接的笨办法
排好了,值从 9 到 3 依次往下。对应的标签变成 1、1、1、2、2、3、3。接下来就从最左边最大的 9 开始,一个一个往右考察。（动画第 5 步）
最优解：一步一步想明白
- 3记牢三步:先按值从大到小排;从大往小扫,标签没满就选、满了就跳;选够 numWanted 就停。标签用没用满,靠一张计数表来查。
- 4这是原始的 7 个项,值的顺序是乱的。贪心要从大值开始,所以第一步先把它们按值从大到小排一遍。
- 5排好了,值从 9 到 3 依次往下。对应的标签变成 1、1、1、2、2、3、3。接下来就从最左边最大的 9 开始,一个一个往右考察。
- 6轮到从左数第 1 个项,它的值是 9,标签是 1。现在已经选了 0 项,和是 0。先去查一下:标签 1 这一组,还能不能再选。
- 7标签 1 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 9 可以收进来。
- 8把 9 收进答案,和从 0 涨到 9,标签 1 的计数加到 1,已选项数变成 1。还没到 5 个,继续往右看。
- 9轮到从左数第 2 个项,它的值是 8,标签是 1。现在已经选了 1 项,和是 9。先去查一下:标签 1 这一组,还能不能再选。
- 10标签 1 目前选了 1 个,还没到上限 2,1 小于 2 成立,所以这个值 8 可以收进来。
- 11把 8 收进答案,和从 9 涨到 17,标签 1 的计数加到 2,已选项数变成 2。还没到 5 个,继续往右看。
- 12轮到从左数第 3 个项,它的值是 7,标签是 1。现在已经选了 2 项,和是 17。先去查一下:标签 1 这一组,还能不能再选。
- 13标签 1 已经选满了 2 个,等于上限 2,2 小于 2 不成立,这个项不能再要了。
- 14所以第 3 项只能放弃,值 7 不计入,和还是 17。注意它被跳过不是因为值小,而是标签 1 的名额用光了。看下一个。
- 15轮到从左数第 4 个项,它的值是 6,标签是 2。现在已经选了 2 项,和是 17。先去查一下:标签 2 这一组,还能不能再选。
- 16标签 2 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 6 可以收进来。
- 17把 6 收进答案,和从 17 涨到 23,标签 2 的计数加到 1,已选项数变成 3。还没到 5 个,继续往右看。
- 18轮到从左数第 5 个项,它的值是 5,标签是 2。现在已经选了 3 项,和是 23。先去查一下:标签 2 这一组,还能不能再选。
- 19标签 2 目前选了 1 个,还没到上限 2,1 小于 2 成立,所以这个值 5 可以收进来。
- 20把 5 收进答案,和从 23 涨到 28,标签 2 的计数加到 2,已选项数变成 4。还没到 5 个,继续往右看。
- 21轮到从左数第 6 个项,它的值是 4,标签是 3。现在已经选了 4 项,和是 28。先去查一下:标签 3 这一组,还能不能再选。
- 22标签 3 目前选了 0 个,还没到上限 2,0 小于 2 成立,所以这个值 4 可以收进来。
- 23把 4 收进答案,和变成 32,标签 3 的计数加到 1。这下已选项数到了 5,正好等于上限 numWanted = 5,不能再选了,扫描就此停下。
- 24扫到选满 5 项就停了,绿色的就是选中的:9、8、6、5、4,加起来等于 32。被划掉的那个是标签名额满了才跳过的;最右边那个 3 因为提前选够了,根本没轮到考察。最终答案 32。
⚠️ 容易写错的地方
✗ 错：只按值贪心,不看标签上限就选
✓ 对：选之前先查该标签已选数 < useLimit
同标签超过 useLimit 个是非法解,会算出比真实答案大的错值
✗ 错：已选满 numWanted 还继续扫
✓ 对：已选数一到 numWanted 立刻停
再选就超过总数上限,且白白多算
✗ 错：把值按从小到大排
✓ 对：必须从大到小排,先考察大值
贪心要先抢大的,升序排会先用掉名额在小值上,和变小
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
int n = values.size();
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; ++i) {
pairs[i] = {-values[i], labels[i]};
}
sort(pairs.begin(), pairs.end());
unordered_map<int, int> cnt;
int ans = 0, num = 0;
for (int i = 0; i < n && num < numWanted; ++i) {
int v = -pairs[i].first, l = pairs[i].second;
if (cnt[l] < useLimit) {
++cnt[l];
++num;
ans += v;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
int n = values.length;
int[][] pairs = new int[n][2];
for (int i = 0; i < n; ++i) {
pairs[i] = new int[] {values[i], labels[i]};
}
Arrays.sort(pairs, (a, b) -> b[0] - a[0]);
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0, num = 0;
for (int i = 0; i < n && num < numWanted; ++i) {
int v = pairs[i][0], l = pairs[i][1];
if (cnt.getOrDefault(l, 0) < useLimit) {
cnt.merge(l, 1, Integer::sum);
num += 1;
ans += v;
}
}
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 受标签影响的最大值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这个贪心为什么是对的,会不会漏掉更优解?+
用交换论证。把项按值从大到小排,贪心照这个顺序、标签有名额且总数没满就选。取第一个「贪心选了、某最优解 OPT 没选」的项 g。OPT 里若 g 的标签还有名额,OPT 为凑够 numWanted 必然选了某个值不超过 g 的项,把它换成 g;若 g 的标签已占满,OPT 必有一个同标签、值不超过 g 的项,把它换成 g。两种情况换完两条上限都不破、总和不减,反复替换就得到含全部贪心选择的最优解,所以贪心最优。
数量上限和标签上限是怎么同时处理的?+
两条上限各管各的。用一个哈希表记每个标签已选数,扫描每个项时双重判断:该标签的计数小于 useLimit,并且已选总数小于 numWanted,两条都满足才把它选进来,总数一到 numWanted 就停止整个扫描。
这题和普通的取前 K 大有什么不同?+
普通取前 K 大只有一个数量约束,排完序直接拿前 K 个就行。这题多了一条「同标签不超过 useLimit」的分组约束,所以排序之后不能照单全收,得边扫边跳过那些标签已经选满的项。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 受标签影响的最大值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。