题目描述
思路解析动画文字版
记牢这一句:排完序后,让最弱的运动员去配够得上他的最弱训练师。这样强的训练师就被省下来留给强运动员,谁都不浪费,配出来的对数就是最多的。下面从最弱的运动员开始,一位一位配。
排序前 · 原始输入：先看没排序的原始数据。上面横排是训练师的能力 7、2、9、3、11、7、4,侧栏是运动员的能力 8、5、13、6、10。这样乱着放没法贪心,贪心的前提是两边都得从小到大排好队,这样才能让最弱的先配最弱的。
排序后 · 两队都从小到大：两边各自排好序。训练师从小到大是 2、3、4、7、7、9、11,运动员从小到大是 5、6、8、10、13。现在准备工作做完了,让指针 j 从最左边的训练师开始,依次给每位运动员找搭档。
开工规则 · 弱运动员配够得上的最弱训练师：规则再明确一下:侧栏最上面高亮的是当前轮到的运动员,永远从最弱的那位开始;主舞台上高亮的是指针 j 当前指着的训练师。给这位运动员找搭档时,j 只会往右走,不回头。够格就染绿配对,太弱就染灰跳过。开始。
轮到运动员 5 · 从训练师 2 开始看：轮到能力 5 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 2 的训练师。看看这位训练师托不托得起 5。
训练师 2 撑不起 5 · 染灰跳过：训练师能力 2 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 3：指针 j 落到能力 3 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
训练师 3 撑不起 5 · 染灰跳过：训练师能力 3 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 4：指针 j 落到能力 4 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
训练师 4 撑不起 5 · 染灰跳过：训练师能力 4 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 7：指针 j 落到能力 7 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
运动员 5 配训练师 7 · 成对!：训练师能力 7 大于等于运动员 5,托得起!这一对成了,把这位训练师染绿。运动员 5 也算配上了。已匹配数加到 1。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 6 · 从训练师 7 开始看：轮到能力 6 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 7 的训练师。看看这位训练师托不托得起 6。
运动员 6 配训练师 7 · 成对!：训练师能力 7 大于等于运动员 6,托得起!这一对成了,把这位训练师染绿。运动员 6 也算配上了。已匹配数加到 2。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 8 · 从训练师 9 开始看：轮到能力 8 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 9 的训练师。看看这位训练师托不托得起 8。
运动员 8 配训练师 9 · 成对!：训练师能力 9 大于等于运动员 8,托得起!这一对成了,把这位训练师染绿。运动员 8 也算配上了。已匹配数加到 3。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 10 · 从训练师 11 开始看：轮到能力 10 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 11 的训练师。看看这位训练师托不托得起 10。
运动员 10 配训练师 11 · 成对!：训练师能力 11 大于等于运动员 10,托得起!这一对成了,把这位训练师染绿。运动员 10 也算配上了。已匹配数加到 4。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 13 · 训练师已用光：轮到能力 13 的运动员,可指针 j 已经扫到训练师队伍的尽头,一个能用的训练师都不剩了。这位运动员再强也没人带,只能落空。
运动员 13 落空 · 结束：既然连最弱的运动员之后的强手都配光了训练师,后面比他更强的运动员更不可能有搭档,直接收工。此刻已经配好的对数就是答案 4。
回放 · 四对配成,答案 4：回看全程。运动员 5、6、8、10 各自配到了一位刚好够得上的训练师,四位训练师染成绿色;被跳过的弱训练师染灰。最强的运动员 13 到最后没有训练师托得起,落空了。数一数绿色的对子,一共 4 对,这就是最大匹配数。
边界想清:训练师少则对数被训练师数卡住、谁都够不上则 0 对、能力相等仍可配成一对。
面试重点:排序加双指针贪心、交换论证证明最优、复杂度由两次排序主导。
参考代码
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 matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int: players.sort() trainers.sort() j, n = 0, len(trainers) for i, p in enumerate(players): while j < n and trainers[j] < p: j += 1 if j == n: return i j += 1 return len(players)复杂度
- 时间：O(m log m + n log n)，m 名运动员、n 位训练师。主要开销是两次排序,分别是 m log m 和 n log n;后面的双指针扫描里 i 和 j 各自只从头走到尾、不回头,是 O(m + n),被排序开销盖过
- 空间：O(1) 辅助 · 排序内部因语言而异，不额外开数组,只用几个指针变量,辅助空间 O(1)。排序内部开销因语言而异:C 加加和 Java 通常是 O(log m + log n) 级的递归栈,Python 的排序最坏可到 O(m + n);若把排序内部也算上,空间随语言在这两档之间
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么这个贪心是对的,能证明吗?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
追加字符以获得子序列
LeetCode 2486 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题