讀完本文，可以去力扣解決如下題目：

870. 優(yōu)勢洗牌（Medium）

田忌賽馬的故事大家應(yīng)該都聽說過：

田忌和齊王賽馬，兩人的馬分上中下三等，如果同等級的馬對應(yīng)著比賽，田忌贏不了齊王。但是田忌遇到了孫臏，孫臏就教他用自己的下等馬對齊王的上等馬，再用自己的上等馬對齊王的中等馬，最后用自己的中等馬對齊王的下等馬，結(jié)果三局兩勝，田忌贏了。

當(dāng)然，這段歷史也挺有意思的，那個諷齊王納諫，自戀的不行的鄒忌和田忌是同一時期的人，他倆后來就杠上了。不過這是題外話，我們這里就打住。

以前學(xué)到田忌賽馬課文的時，我就在想，如果不是三匹馬比賽，而是一百匹馬比賽，孫臏還能不能合理地安排比賽的順序，贏得齊王呢？

當(dāng)時沒想出什么好的點子，只覺得這里面最核心問題是要盡可能讓自己占便宜，讓對方吃虧。總結(jié)來說就是，打得過就打，打不過就拿自己的垃圾和對方的精銳互換。

不過，我一直沒具體把這個思路實現(xiàn)出來，直到最近刷到力扣第 870 題「優(yōu)勢洗牌」，一眼就發(fā)現(xiàn)這是田忌賽馬問題的加強(qiáng)版：

給你輸入兩個長度相等的數(shù)組nums1和nums2，請你重新組織nums1中元素的位置，使得nums1的「優(yōu)勢」最大化。

如果nums1[i] > nums2[i]，就是說nums1在索引i上對nums2[i]有「優(yōu)勢」。優(yōu)勢最大化也就是說讓你重新組織nums1，盡可能多的讓nums[i] > nums2[i]。

算法簽名如下：

int[]?advantageCount(int[]?nums1,?int[]?nums2);
比如輸入：

nums1 = [12,24,8,32]
nums2 = [13,25,32,11]

你的算法應(yīng)該返回[24,32,8,12]，因為這樣排列nums1的話有三個元素都有「優(yōu)勢」。

這就像田忌賽馬的情景，nums1就是田忌的馬，nums2就是齊王的馬，數(shù)組中的元素就是馬的戰(zhàn)斗力，你就是孫臏，展示你真正的技術(shù)吧。

仔細(xì)想想，這個題的解法還是有點撲朔迷離的。什么時候應(yīng)該放棄抵抗去送人頭，什么時候應(yīng)該硬剛？這里面應(yīng)該有一種算法策略來最大化「優(yōu)勢」。

送人頭一定是迫不得已而為之的權(quán)宜之計，否則隔壁田忌就要開語音罵你菜了。只有田忌的上等馬比不過齊王的上等馬時，所以才會用下等馬去和齊王的上等馬互換。

對于比較復(fù)雜的問題，可以嘗試從特殊情況考慮。

你想，誰應(yīng)該去應(yīng)對齊王最快的馬？肯定是田忌最快的那匹馬，我們簡稱一號選手。

如果田忌的一號選手比不過齊王的一號選手，那其他馬肯定是白給了，顯然這種情況肯定應(yīng)該用田忌墊底的馬去送人頭，降低己方損失，保存實力，增加接下來比賽的勝率。

但如果田忌的一號選手能比得過齊王的一號選手，那就和齊王硬剛好了，反正這把田忌可以贏。

你也許說，這種情況下說不定田忌的二號選手也能干得過齊王的一號選手？如果可以的話，讓二號選手去對決齊王的一號選手，不是更節(jié)約？

就好比，如果考 60 分就能過的話，何必考 61 分？每多考一分就虧一分，剛剛好卡在 60 分是最劃算的。

這種節(jié)約的策略是沒問題的，但是沒有必要。這也是本題有趣的地方，需要繞個腦筋急轉(zhuǎn)彎：

我們暫且把田忌的一號選手稱為T1，二號選手稱為T2，齊王的一號選手稱為Q1。

如果T2能贏Q1，你試圖保存己方實力，讓T2去戰(zhàn)Q1，把T1留著是為了對付誰？

顯然，你擔(dān)心齊王還有戰(zhàn)力大于T2的馬，可以讓T1去對付。

但是你仔細(xì)想想，現(xiàn)在T2已經(jīng)是可以戰(zhàn)勝Q1的了，Q1可是齊王的最快的馬耶，齊王剩下的那些馬里，怎么可能還有比T2更強(qiáng)的馬？

所以，沒必要節(jié)約，最后我們得出的策略就是：

將齊王和田忌的馬按照戰(zhàn)斗力排序，然后按照排名一一對比。如果田忌的馬能贏，那就比賽，如果贏不了，那就換個墊底的來送人頭，保存實力。

上述思路的代碼邏輯如下：

int?n?=?nums1.length;

sort(nums1);?//?田忌的馬
sort(nums2);?//?齊王的馬

//?從最快的馬開始比
for?(int?i?=?n?-?1;?i?>=?0;?i--)?{
????if?(nums1[i]?>?nums2[i])?{
????????//?比得過，跟他比
????}?else?{
????????//?比不過，換個墊底的來送人頭
????}
}
根據(jù)這個思路，我們需要對兩個數(shù)組排序，但是nums2中元素的順序不能改變，因為計算結(jié)果的順序依賴nums2的順序，所以不能直接對nums2進(jìn)行排序，而是利用其他數(shù)據(jù)結(jié)構(gòu)來輔助。

同時，最終的解法還用到前文 雙指針技巧匯總 總結(jié)的雙指針?biāo)惴０?，用以處理「送人頭」的情況：

int[]?advantageCount(int[]?nums1,?int[]?nums2)?{
????int?n?=?nums1.length;
????//?給?nums2?降序排序
????PriorityQueue<int[]>?maxpq?=?new?PriorityQueue<>(
????????(int[]?pair1,?int[]?pair2)?->?{?
????????????return?pair2[1]?-?pair1[1];
????????}
????);
????for?(int?i?=?0;?i?????????maxpq.offer(new?int[]{i,?nums2[i]});
????}
????//?給?nums1?升序排序
????Arrays.sort(nums1);

????//?nums1[left]?是最小值，nums1[right]?是最大值
????int?left?=?0,?right?=?n?-?1;
????int[]?res?=?new?int[n];

????while?(!maxpq.isEmpty())?{
????????int[]?pair?=?maxpq.poll();
????????//?maxval?是?nums2?中的最大值，i?是對應(yīng)索引
????????int?i?=?pair[0],?maxval?=?pair[1];
????????if?(maxval?????????????//?如果?nums1[right]?能勝過?maxval，那就自己上
????????????res[i]?=?nums1[right];
????????????right--;
????????}?else?{
????????????//?否則用最小值混一下，養(yǎng)精蓄銳
????????????res[i]?=?nums1[left];
????????????left ;
????????}
????}
????return?res;
}
算法的時間復(fù)雜度很好分析，也就是二叉堆和排序的復(fù)雜度O(nlogn)。

至此，這道田忌賽馬的題就解決了，其代碼實現(xiàn)上用到了雙指針技巧，從最快的馬開始，比得過就比，比不過就送，這樣就能對任意數(shù)量的馬求取一個最優(yōu)的比賽策略了。

好了，田忌賽馬的問題沒什么可說的了，有興趣不妨了解下田忌和鄒忌的故事，值得思考。

＿＿＿＿＿＿＿＿＿＿＿＿＿