题目描述
思路解析动画文字版
口诀:能赢就赢、赢不了就用最弱的去送。下面每帧都在套它。
这是我方马的原始顺序,乱的。第一步先把它们从弱到强排序,方便「先派弱马」。
我方马排好了,从弱到强是 [ 2, 5, 9, 11, 14, 20 ]。最弱的 2 排最前,最强的 20 排最后。
这是对手马,顺序是固定的,因为答案要一一对位。我们要记住每匹对手马的原始位置,赢谁、送谁都要把我方马填回对手那个位置上。
把对手也从弱到强排一份(原始位置另记着)。架两个指针:i 指对手当前最弱的马、j 指当前最强的马,从两头往中间夹。答案数组 ans 先全空着。
开战!两队都从弱到强排好,对手两端架上 i、j 指针。我方按从弱到强的顺序一匹匹上场,第一匹是最弱的 2。
轮到我方目前最弱的马 2(侧栏高亮)。先看对手当前最弱的马 6。2 连对手最弱的 6 都赢不了,说明它谁也赢不了。既然是废棋,就拿去送给对手最强的马。
把 2 送给对手最强的 19(它的原始位置 3),这场我们认输、标红,但用一匹废马换掉了对手的王牌。j 左移,下次对手的「最强」就换成更小的了。ans 第 3 位填上 2。
轮到我方目前最弱的马 5(侧栏高亮)。先看对手当前最弱的马 6。5 连对手最弱的 6 都赢不了,说明它谁也赢不了。既然是废棋,就拿去送给对手最强的马。
把 5 送给对手最强的 15(它的原始位置 5),这场我们认输、标红,但用一匹废马换掉了对手的王牌。j 左移,下次对手的「最强」就换成更小的了。ans 第 5 位填上 5。
轮到我方目前最弱的马 9(侧栏高亮)。先看对手当前最弱的马 6。9 比 6 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
成交!把 9 安排去赢对手的 6(它的原始位置 2),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 2 位填上 9。
轮到我方目前最弱的马 11(侧栏高亮)。先看对手当前最弱的马 7。11 比 7 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
成交!把 11 安排去赢对手的 7(它的原始位置 4),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 4 位填上 11。
轮到我方目前最弱的马 14(侧栏高亮)。先看对手当前最弱的马 8。14 比 8 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
成交!把 14 安排去赢对手的 8(它的原始位置 0),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 0 位填上 14。
轮到我方目前最弱的马 20(侧栏高亮)。先看对手当前最弱的马 12。20 比 12 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
成交!把 20 安排去赢对手的 12(它的原始位置 1),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 1 位填上 20。
全部安排完毕。绿格是我们赢下的 4 场,从左边长出来;红格是送掉的 2 场,从右边长出来,两边在中间会合。优势 = 绿格数 = 4,已经是最大值。
换个角度看我方马:绿色这几匹去赢了对手,红色这几匹是赢不了被拿去送的。注意被送的都是最弱的那几匹,强马一匹没浪费。
这就是最终的 ans。它是按对手原始位置填出来的,所以直接和原始 nums2 对位:绿表示这一位我方更大、赢了。数一数,赢的正好是 4 场。
最后回到对手的原始顺序 nums2。绿格是我方那一位更大、拿下优势的位置,一共 4 个,这就是最大优势。红格是认输的位置,已被我们的废马占着,一分没多送。
边界先想清:全能赢、全赢不了、单元素三种极端。
面试重点:讲清「赢不了的就去消耗对手王牌」这步为什么不亏。
参考代码
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 advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() t = sorted((v, i) for i, v in enumerate(nums2)) n = len(nums2) ans = [0] * n i, j = 0, n - 1 for v in nums1: if v <= t[i][0]: ans[t[j][1]] = v j -= 1 else: ans[t[i][1]] = v i += 1 return ans复杂度
- 时间：O(n log n)，两次排序是瓶颈,之后一趟线性扫描
- 空间：O(n)，存对手的(值,原始下标)配对以及答案数组
易错点
面试追问把动画讲成自己的话
追问这道贪心的正确性怎么直观说明?
追问和「分发饼干」「用最少的箭引爆气球」这类题有什么共性?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
三数之和的多种可能
LeetCode 923 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题