刷 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^5，k 最大也是 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(key=lambda x: x[1], reverse=True)。需要注意一个细节：如果两个工程师效率相等，他们之间的先后顺序其实不影响结果，因为当他们的效率都相同时，最小效率相同，候选池也相同。但为了代码稳定和常数小一点，有些实现会顺便按速度降序排列，这会让速度较快的工程师更早进入候选池，操作起来顺手一些。
扫描时，维护一个变量 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(key=lambda x: x[1], reverse=True) 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^5，k 是 10^5，所以速度之和最大是 10^10，已经超出 int 的表示了。乘上效率最大值 10^5，结果最高能到 10^15。因此 speed_sum 和 ans 都必须声明为 long long。下面是一个标准的 C++ 版本：
class Solution { public: int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) { vector<pair<int, int>> people(n); for (int i = 0; i < n; ++i) { people[i] = {speed[i], efficiency[i]}; } // 按效率降序排序 sort(people.begin(), people.end(), [](const pair<int, int>& a, const pair<int, int>& b) { if (a.second != b.second) return a.second > b.second; return a.first > b.first; }); priority_queue<int, vector<int>, greater<int>> 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 的模板参数是greater<int>，代表小顶堆。这里不要手滑写成默认的less<int>，否则变成大顶堆，维护逻辑就完全反了。另外排序比较函数里，我给效率相等的情况加了一个按速度降序的第二关键字，这一步可以不做，不会影响正确性，但能稍微提升一点运行效率，让更有价值的人更早进入堆。
3.3 手算一个完整样例，验证流程
光看代码还是不够踏实，我建议新手朋友把一个小例子从头到尾手算一遍。假设 n = 3，k = 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，弹出堆顶也就是最小的 1，speed_sum 减去 1 变成 5。此时堆里是 [2, 3]，速度较慢的第三个工程师被淘汰了。当前最小效率是 3，表现值 5 × 3 = 15，答案保持 25。
最终答案是 25。手动枚举所有组合验证一下：选第一个和第二个工程师，速度 3+1=4，最小效率 min(5,3)=3，乘积 12；选第一个和第三个工程师，速度 3+2=5，最小效率 min(5,6)=5，乘积 25；选第二个和第三个工程师，速度 1+2=3，最小效率 min(3,6)=3，乘积 9；只选第一个是 3×5=15，只选第二个是 1×3=3，只选第三个是 2×6=12。最大值确实是 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、速度全相等、效率全相等这些极端情况一次性测完。这种题翻车概率最高的点不在算法推导，而在实现细节。这些细节踩过一次坑，以后遇到同类型问题，就能少走很多弯路。
