刷 LeetCode 的朋友应该对“困难题”这三个字又爱又恨。爱的是解出来确实爽恨的是很多时候连题都读不懂。今天聊的这道 1383. Maximum Performance of a Team中文名叫“最大的团队表现值”属于那种典型的“看起来不难自己一写就卡住”的题。它在 LeetCode 上是困难标签但核心思路并不玄乎排序加贪心再用一个堆来维护候选集合。如果你正在准备面试或者刷题想从“背模板”进阶到“懂思路”这道题值得好好拆一遍。题目本身是这么个场景你有 n 个工程师每个工程师有两个属性——速度 speed 和效率 efficiency。现在要组建一个团队人数不超过 k团队表现值等于所有人速度之和乘以团队里最小的那个效率值。我们要在所有的组队方案里找出这个乘积的最大值。注意两个关键词人数“不超过 k”以及是“最小效率”而非平均效率。第一个关键词决定了我们不一定非要选满 k 个人第二个关键词是整道题的核心矛盾所在。我先说结论这道题的最优解法是先按效率从大到小排序然后逐个扫描工程师用一个大小为 k 的最小堆来维护当前速度最大的至多 k 个人。扫描过程中不断用“当前速度之和 × 当前工程师的效率”去更新答案。整个过程只需要 O(n log k) 的时间。下面我会详细解释为什么这个做法是对的以及里面有哪些坑是必须避开的。1. 题目理解与初始思路拆解1.1 两个因素的互相牵制先模拟一下普通人拿到这道题的第一反应。如果是我的话会试图枚举所有可能的团队组合然后计算每个组合的表现值取最大。但 n 的范围是 1 到 10^5k 最大也是 10^5组合数 C(n,k) 是个天文数字直接枚举完全不可行。那能不能按某个指标贪心呢比如我先把工程师按速度排序选速度最快的 k 个人这样看起来速度之和最大化了但完全忽略了效率。假设你选的这 k 个人里混进来一个效率只有 1 的“拖油瓶”就算其他人都是效率 100整个团队的最小效率也被拉到了 1最后乘积直接崩盘。反过来只按效率选人速度之和可能又低得离谱。这两个指标是互相牵制的一个想往大了选一个怕被最小值卡死单看任何一个维度都会得出错误答案。这道题难就难在“乘积”这个结构上。速度和是累加出来的效率是取最小值两者混在一起常规的排序贪心失灵了。我一开始拿到这题也走了弯路先试过按速度排序再调整又试过按效率分桶暴力算最后才想到要固定一个变量再在另一个变量上做文章。1.2 固定最小效率问题立刻简化既然“团队最小效率”是个门槛那我们不妨反过来想假设我已经知道团队里效率最低的那个人是谁那团队的效率值就是这个人的效率 e[i]。此时所有效率大于等于 e[i] 的工程师都可以成为团队成员那些效率更低的直接排除在外。在这个候选池里为了让速度之和最大我需要选速度最大的至多 k 个人。也就是说一旦确定了“谁是团队里效率最低的人”剩下的问题就变成一个单纯的“在若干候选人里挑速度最大的几个人”的问题这是可以用堆解决的。这时候你可能要问了我怎么知道谁是效率最低的人总不能对每个工程师都假设一遍然后重新筛选吧。这里就需要排序了。如果先把所有工程师按效率从高到低排序然后从左往右扫描那么扫描到第 i 个工程师时当前已经扫过的所有工程师的效率都大于等于当前人的效率。换句话说当前这个工程师就是已经扫过的这批人里效率最低的那个。于是“枚举最小效率”这个操作就被排序后的单向扫描天然实现了。我可以用一个生活化的类比想象你在举办一个选秀比赛参赛者水平参差不齐。你从水平最高的选手开始一个个往后看。每看到一个选手你就把他放进候选人名单里同时假设当前看到的这个选手就是你最后定下的“团队下限”。这个过程里你每前进一个位置门槛就降低一点候选人名单会越来越长。每次更新门槛后你只需要在候选人名单里挑综合实力最强的几个去组队看看这个方案能不能刷新纪录。这个“排序 单向扫描”的思路把二维的双因素优化问题降成了一维的贪心问题是这道题真正的题眼。下面进入具体的算法设计。2. 算法设计详解2.1 为什么优先队列堆选择最小堆先明确一下我们要维护的到底是什么。在扫描过程中候选池是动态增长的而我们只关心候选池里速度最大的至多 k 个工程师。这个偏好的本质是在数量受限的情况下保住最大值丢掉最小值。正是“丢掉最小值”这个动作决定了我们应该使用最小堆。最小堆的堆顶是堆中最小的元素所以当新来一个工程师时我可以快速判断如果他的速度比堆顶还小那说明他挤不进当前最快的 k 人名单可以直接忽略如果他的速度比堆顶大就把他加进来然后把堆顶弹出这样堆里永远保持着“当前见过的工程师里速度最大的 k 个人”。整个过程里堆内元素个数永远不超过 k堆顶元素永远是当前候选组里速度最慢的那一个换人成本极低。有同学可能会问为什么不用最大堆如果我用最大堆堆顶确实是最大的但我想知道的是“哪些人相对较弱应该被淘汰”最大堆给不了这个信息。所以最小堆才是正确的选择这也是很多新手写不出这题的关键原因之一。2.2 排序规则与扫描顺序的选择排序的键是效率方向是从大到小。这一步的意义前面已经讲过它保证了扫描到任何位置 i 时当前工程师的效率是已处理集合中的最小值于是可以直接把当前效率当作团队的最小效率来计算。如果你用 C 写排序时可以用 pair 打包速度与效率然后自定义比较函数按效率降序排列。Python 里更简单直接传 key 参数或者用 sort(keylambda x: x[1], reverseTrue)。需要注意一个细节如果两个工程师效率相等他们之间的先后顺序其实不影响结果因为当他们的效率都相同时最小效率相同候选池也相同。但为了代码稳定和常数小一点有些实现会顺便按速度降序排列这会让速度较快的工程师更早进入候选池操作起来顺手一些。扫描时维护一个变量 speed_sum 表示当前堆内所有工程师速度之和。每次加入一个新工程师就把 speed_sum 加上他的速度如果堆的大小超过 k就弹出堆顶速度最慢的人并从 speed_sum 中减去该弹出者的速度。然后用当前的 speed_sum 乘以当前工程师的效率得到候选答案更新全局最大值。说到这里要强调一个容易被忽略的点题目说的是“人数至多 k”不是“恰好 k”。这意味着当候选池人数还不足 k 时我们可以直接把所有人都选进团队不需要强行凑数。对应到代码里就是当堆的大小小于等于 k 时直接计算答案即可只在堆大小等于 k 1 时才弹出堆顶。我在初写代码时就把这个细节理解错了堆大小小于 k 也强行 pop导致一些样例结果偏小后面会专门讲这个问题。2.3 贪心正确性的论证这类“最小堆 排序”的解法代码写出来可能不到三十行但面试时最怕被追问“你凭啥觉得这样是对的”所以我想把正确性证明也讲透免得你好不容易学会了面试官一追问又卡壳。可以这样论证。假设存在一个最优团队它的最小效率是 e_min。因为团队里所有人的效率都大于等于 e_min所以这个团队里的所有工程师在我们扫描到那个效率恰好为 e_min 的工程师时都已经进入过候选池了。而我们的算法在每个时刻都会在当前候选池中维护一个“速度最大的至多 k 个人”的集合。这个集合的速度之和一定不小于那个最优团队的速度之和因为最优团队也至多是候选池里选出的若干人而我们的堆选的是同一批候选人里速度最大的那批。既然最小效率相同都是 e_min我们的方案速度之和又不差于最优方案那么两者相乘我们的结果一定不差于最优方案。所以全局最大值一定会被覆盖到。再通俗一点说最优解无论长什么样它对应的“最小效率”那一刻算法已经把那一刻能挑到的最强组合算过了所以答案不可能落后。从反方向理解也可以如果某时刻我们选的不是候选池里速度最大的几个人而是选了速度较慢的人那么把其中一个人换成速度更快的候选人总速度会变大而最小效率保持不变因为团队的最小效率由当前扫描到的那个效率最低的人决定表现值只会变大。这说明最优决策一定是选速度最大的一批人贪心不会把好答案丢掉。3. 完整题解与关键实现细节3.1 可运行的 Python 参考实现如果面试用的是 Python代码非常短。下面是完整实现我加了详细的注释方便你直接理解每一步在干什么。class Solution: def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) - int: # 将速度和效率打包按效率从高到低排序 people list(zip(speed, efficiency)) people.sort(keylambda x: x[1], reverseTrue) import heapq heap [] # 最小堆维护当前速度最大的最多 k 个人 speed_sum 0 # 堆中所有人的速度之和 ans 0 # 真实的最大值先不取模 for s, e in people: # 把当前工程师加入候选 heapq.heappush(heap, s) speed_sum s # 如果人数超过了 k弹出速度最慢的人 if len(heap) k: speed_sum - heapq.heappop(heap) # 当前 e 是团队的最小效率更新答案 ans max(ans, speed_sum * e) return ans % (10**9 7)这里面有个细节值得注意ans 在更新时用的是没有取模的真实值最后返回时才取模。原因很简单如果在中途每一步都对 ans 取模那么取模后的数字大小关系就乱了max 也就失去了意义。因为这个乘法的最大量级是 10 的 15 次方左右用 Python 的大整数完全没问题所以真实值的比较没有任何负担。3.2 可运行的 C 参考实现如果你平时用 C 刷题需要注意一个非常隐蔽的坑int 溢出。speed 的最大值是 10^5k 是 10^5所以速度之和最大是 10^10已经超出 int 的表示了。乘上效率最大值 10^5结果最高能到 10^15。因此 speed_sum 和 ans 都必须声明为 long long。下面是一个标准的 C 版本class Solution { public: int maxPerformance(int n, vectorint speed, vectorint efficiency, int k) { vectorpairint, int people(n); for (int i 0; i n; i) { people[i] {speed[i], efficiency[i]}; } // 按效率降序排序 sort(people.begin(), people.end(), [](const pairint, int a, const pairint, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; }); priority_queueint, vectorint, greaterint pq; // 最小堆 long long speedSum 0; long long ans 0; for (auto [s, e] : people) { pq.push(s); speedSum s; if (pq.size() k) { speedSum - pq.top(); pq.pop(); } ans max(ans, speedSum * e); } return (int)(ans % 1000000007); } };C 版本里 priority_queue 的模板参数是greaterint代表小顶堆。这里不要手滑写成默认的lessint否则变成大顶堆维护逻辑就完全反了。另外排序比较函数里我给效率相等的情况加了一个按速度降序的第二关键字这一步可以不做不会影响正确性但能稍微提升一点运行效率让更有价值的人更早进入堆。3.3 手算一个完整样例验证流程光看代码还是不够踏实我建议新手朋友把一个小例子从头到尾手算一遍。假设 n 3k 2速度分别是 [3, 1, 2]效率分别是 [5, 3, 6]。先把人和效率打包排序得到排序后的数组为(速度 2效率 6)(速度 3效率 5)(速度 1效率 3)然后逐步模拟第一步扫描 (2, 6)推入堆speed_sum 2堆内元素 [2]。用 2 × 6 12 更新答案。这里的含义是我只选了第一个工程师一个人效率是 6速度是 2表现值 12。第二步扫描 (3, 5)推入堆speed_sum 5堆内元素 [2, 3]。堆大小等于 k 2没有触发弹出。注意此时的最小效率是当前扫描到的 5也就是第二个工程师的效率表现值 5 × 5 25更新答案。第三步扫描 (1, 3)推入堆speed_sum 6堆内元素 [2, 3, 1]。堆大小超过了 k弹出堆顶也就是最小的 1speed_sum 减去 1 变成 5。此时堆里是 [2, 3]速度较慢的第三个工程师被淘汰了。当前最小效率是 3表现值 5 × 3 15答案保持 25。最终答案是 25。手动枚举所有组合验证一下选第一个和第二个工程师速度 314最小效率 min(5,3)3乘积 12选第一个和第三个工程师速度 325最小效率 min(5,6)5乘积 25选第二个和第三个工程师速度 123最小效率 min(3,6)3乘积 9只选第一个是 3×515只选第二个是 1×33只选第三个是 2×612。最大值确实是 25。整个流程和答案完全吻合。4. 常见问题与排查技巧实录4.1 为什么答案要用 long long取模时机怎么把握这题我见群里很多朋友第一次提交就挂在溢出上。他们在 C 里声明了int speedSum 0结果跑到后面 speedSum 变成负数或者乱掉怎么查都查不出来。实际上就是因为速度之和轻松突破 int 的限制。记住一个经验公式只要题目里存在“多个最大值相加再相乘”先估算量级别嫌麻烦直接用 long long。至于 Python虽然不担心大整数但如果你在更新答案时先取模再比较大小也会得到错误答案。正确做法就是我代码里的那样全程用真实值比较最后返回前一次性取模。4.2 堆大小小于 k 时要不要弹出堆顶这是我踩过的第二个坑。有些题解写的是“当堆大小等于 k 时弹出”有些写的是“当堆大小超过 k 时弹出”表面上看差别不大实际上后者才是正确写法。因为题目允许“至多 k 人”当候选池人数不足 k 时我们应该全部选进来表现值可能更大。如果强行弹出一个人速度之和变小了而最小效率没有变结果只会变差。所以记住只有堆的大小达到 k 1 时才弹出堆顶。4.3 效率相同时排序顺序会不会影响答案这个不用担心。假设有两个工程师效率都是 5一个速度 100一个速度 10。无论先把谁放进候选池我们在处理第二个人的时候两个人的速度都已经在堆里了最后选出来的人不会因为谁先谁后而改变。不过从代码风格上讲效率相同时按速度降序排会让堆里的替换操作更少一些实测常数也更小。这道题的 n 有 10^5排序已经是 O(n log n) 了常数优化意义不大但养成好习惯不亏。4.4 极端场景只选一个人或者可以全选当 k 1 时堆里永远只有一个人speed_sum 就是当前这个人的速度答案就是单个工程师的 speed × efficiency 的最大值。这个场景下排序后扫描依然正确堆的替换操作也符合直觉。当 k 大于等于 n 时堆永远不会超过 k也就是任何工程师都不会被弹出算法等价于“按效率降序遍历选所有已见候选人中速度最大的集合”。注意即使可以选所有人也不是一定要选所有候选人因为后面加入的速度很慢、效率又低的工程师可能拉低最小效率导致乘积变小但由于我们保留了历史最大值答案不会被这种负数影响。我的建议是把这两种边界场景写进测试用例里跑一遍确认输出符合直觉再提交。4.5 在堆中只存速度真的够吗只存速度就足够了因为堆的作用仅仅是维护“哪些人应该留在候选名单里”。候选名单里的人具体是谁我们其实不需要知道只要知道速度和就能算表现值。有人可能会担心如果两个工程师速度一样只是效率不同堆的弹出会不会丢失某个本该保留的人不会。效率已经通过排序处理了当前扫描到的人是效率最低的堆里的人效率都大于等于他。速度相同的情况下弹出任何一个对速度之和没有影响对最终答案也没有影响。所以只存速度是一个非常干净的抽象。5. 拓展延伸与面试实战心得5.1 这类“排序 堆”模型还能套用到哪些题刷题多了你会发现LeetCode 上有好几道中等偏难的题都是同一个套路双因素优化先排序固定一个因素然后用堆去贪心另一个因素。比如“安排会议的最多场次”1353、“最大数”179、“IPO”502等或多或少都能看到这种影子。遇到这类题我的破题顺序一般是先问自己能不能暴力枚举再看能不能固定其中一个维度如果能剩下的问题通常就是“在一个动态集合里维护前 k 大元素”堆自然就上场了。回到这题如果把题意改一改比如把“最小效率”改成“平均效率”或者把“至多 k 人”改成“至少 k 人”解法就要相应调整了。最小效率和平均效率虽然都是“团队整体水平”的一种度量但因为平均效率不是由某一个人单方面决定排序扫描的优雅性质就会被打破。面试时如果被问到变体可以先尝试在排序逻辑上做文章再考虑是否需要离线处理或者二分答案。5.2 面试现场如何一步步推导出这个解法如果面试官给出这道题我建议你先讲最蠢的暴力做法枚举所有组合复杂度是组合数级别n 稍微大一点就跑不动。然后提出一个关键观察团队表现值的瓶颈是最小效率所以不妨假设某个工程师就是最小效率。这个假设一旦说出来后续的排序和堆就水到渠成了。在纸上画一个按效率降序排列的数组模拟两个工程师的进出操作面试官立刻就能看到你的思路是连贯的。不要一上来就背代码。代码只是最后十秒钟的事情真正拉开差距的是你在推导过程中展示的“为什么排序”以及“为什么用最小堆而不是最大堆”这两个判断。我面试别人时最在意的也是候选人能否讲清楚取舍背后的权衡。5.3 一道题的三层收获我在反复刷这道题的过程中感到最重要的收获有三层。第一层是模型认知双约束优化问题可以通过固定一个约束来降维。第二层是工具手感什么时候用最小堆、什么时候用最大堆、堆里存什么全都是有明确目的的不是套模板。第三层是代码谨慎度溢出、取模时机、边界条件这些在工程里同样重要。给你一个具体的刷题建议第一遍自己独立思考哪怕写不出来也要把卡住的地方记录下来第二遍对照上面的代码逐行理解尤其是 pop 的时机第三遍合上答案用不同的语言或不同的思路重写一遍。三遍之后这道题就不再是一道“需要背的困难题”而是你脑海里一个清晰的算法模型。最后再分享一个小技巧如果你的在线评测环境支持自定义测试用例一定要把 k 1、k n、n 1、速度全相等、效率全相等这些极端情况一次性测完。这种题翻车概率最高的点不在算法推导而在实现细节。这些细节踩过一次坑以后遇到同类型问题就能少走很多弯路。