读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
870. 劣势洗牌（中等）
———–
田忌赛马的故事大家应该都据说过：
田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着较量，田忌赢不了齐王。然而田忌遇到了孙膑，孙膑就教他用本人的下等马对齐王的上等马，再用本人的上等马对齐王的中等马，最初用本人的中等马对齐王的下等马，后果三局两胜，田忌赢了。
当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一期间的人，他俩起初就杠上了。不过这是题外话，咱们这里就打住。
以前学到田忌赛马课文的时，我就在想，如果不是三匹马较量，而是一百匹马较量，孙膑还能不能正当地安顿较量的程序，博得齐王呢？
过后没想出什么好的点子，只感觉这外面最外围问题是要尽可能让本人占便宜，让对方吃亏。总结来说就是，打得过就打，打不过就拿本人的垃圾和对方的精锐调换。
不过，我始终没具体把这个思路实现进去，直到最近刷到力扣第 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，欢送点赞！