共计 2914 个字符，预计需要花费 8 分钟才能阅读完成。
读完本文，能够去力扣解决如下题目：
870. 劣势洗牌（Medium）
田忌赛马的故事大家应该都据说过：
田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着较量，田忌赢不了齐王。然而田忌遇到了孙膑，孙膑就教他用本人的下等马对齐王的上等马，再用本人的上等马对齐王的中等马，最初用本人的中等马对齐王的下等马，后果三局两胜，田忌赢了。
当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一期间的人，他俩起初就杠上了。不过这是题外话，咱们这里就打住。
以前学到田忌赛马课文的时，我就在想，如果不是三匹马较量，而是一百匹马较量，孙膑还能不能正当地安顿较量的程序，博得齐王呢？
过后没想出什么好的点子，只感觉这外面最外围问题是要尽可能让本人占便宜，让对方吃亏。总结来说就是，打得过就打，打不过就拿本人的垃圾和对方的精锐调换。
不过，我始终没具体把这个思路实现进去，直到最近刷到力扣第 870 题「劣势洗牌」，一眼就发现这是田忌赛马问题的加强版：
给你输出两个 长度相等 的数组 nums1 和nums2，请你从新组织 nums1 中元素的地位，使得 nums1 的「劣势」最大化。
如果 nums1[i] > nums2[i]，就是说nums1 在索引 i 上对 nums2[i] 有「劣势」。劣势最大化也就是说让你从新组织 nums1， 尽可能多的让nums[i] > nums2[i]。
算法签名如下：
int[] advantageCount(int[] nums1, int[] nums2);
比方输出：
nums1 = [12,24,8,32] nums2 = [13,25,32,11]
你的算法应该返回 [24,32,8,12]，因为这样排列nums1 的话有三个元素都有「劣势」。
这就像田忌赛马的情景，nums1就是田忌的马，nums2就是齐王的马，数组中的元素就是马的战斗力，你就是孙膑，展现你真正的技术吧。
认真想想，这个题的解法还是有点错综复杂的。什么时候应该放弃抵制去送人头，什么时候应该硬刚？这外面应该有一种算法策略来最大化「劣势」。
送人头肯定是迫不得已而为之的权宜之计，否则隔壁田忌就要开语音骂你菜了。只有田忌的上等马比不过齐王的上等马时，所以才会用下等马去和齐王的上等马调换。
对于比较复杂的问题，能够尝试从非凡状况思考。
你想，谁应该去应答齐王最快的马？必定是田忌最快的那匹马，咱们简称一号选手。
如果田忌的一号选手比不过齐王的一号选手，那其余马必定是白给了，显然这种状况必定应该用田忌垫底的马去送人头，升高己方损失，保存实力，减少接下来较量的胜率。
但如果田忌的一号选手能比得过齐王的一号选手，那就和齐王硬刚好了，反正这把田忌能够赢。
你兴许说，这种状况下说不定田忌的二号选手也无能得过齐王的一号选手？如果能够的话，让二号选手去对决齐王的一号选手，不是更节约？
就好比，如果考 60 分就能过的话，何必考 61 分？每多考一分就亏一分，刚刚好卡在 60 分是最划算的。
这种节约的策略是没问题的，然而没有必要。这也是本题乏味的中央，须要绕个脑筋急转弯：
咱们暂且把田忌的一号选手称为T1，二号选手称为T2，齐王的一号选手称为Q1。
如果 T2 能赢 Q1，你试图保留己方实力，让T2 去战 Q1，把T1 留着是为了凑合谁？
显然，你放心齐王还有战力大于 T2 的马，能够让 T1 去凑合。
然而你认真想想，当初 T2 曾经是能够战败 Q1 的了，Q1可是齐王的最快的马耶，齐王剩下的那些马里，怎么可能还有比 T2 更强的马？
所以，没必要节约，最初咱们得出的策略就是：
将齐王和田忌的马依照战斗力排序，而后依照排名一一比照。如果田忌的马能赢，那就较量，如果赢不了，那就换个垫底的来送人头，保存实力。
上述思路的代码逻辑如下：
int n = nums1.length;
sort(nums1); // 田忌的马
sort(nums2); // 齐王的马
// 从最快的马开始比
for (int i = n - 1; i >= 0; i--) {if (nums1[i] > nums2[i]) {// 比得过，跟他比} else {// 比不过，换个垫底的来送人头}
}
依据这个思路，咱们须要对两个数组排序，然而 nums2 中元素的程序不能扭转，因为计算结果的程序依赖 nums2 的程序，所以不能间接对 nums2 进行排序，而是利用其余数据结构来辅助。
同时，最终的解法还用到前文 双指针技巧汇总 总结的双指针算法模板，用以解决「送人头」的状况：
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 < n; 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 是对应索引
int i = pair[0], maxval = pair[1];
if (maxval < nums1[right]) {// 如果 nums1[right] 能胜过 maxval，那就本人上
res[i] = nums1[right];
right--;
} else {
// 否则用最小值混一下，竭尽全力
res[i] = nums1[left];
left++;
}
}
return res;
}
算法的工夫复杂度很好剖析，也就是二叉堆和排序的复杂度O(nlogn)。
至此，这道田忌赛马的题就解决了，其代码实现上用到了双指针技巧，从最快的马开始，比得过就比，比不过就送，这样就能对任意数量的马求取一个最优的较量策略了。
好了，田忌赛马的问题没什么可说的了，有趣味无妨理解下田忌和邹忌的故事，值得思考。
查看更多优质算法文章 点击这里，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！