870. Advantage Shuffle (M)

https://leetcode.com/problems/advantage-shuffle/

You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].

Return any permutation of nums1 that maximizes its advantage with respect to nums2.

Example 1:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

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

Constraints:

• 1 <= nums1.length <= 105

• nums2.length == nums1.length

• 0 <= nums1[i], nums2[i] <= 109

Solution:

田忌赛马的故事大家应该都听说过：

田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。

当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一时期的人，他俩后来就杠上了。不过这是题外话，我们这里就打住。

以前学到田忌赛马课文的时，我就在想，如果不是三匹马比赛，而是一百匹马比赛，孙膑还能不能合理地安排比赛的顺序，赢得齐王呢？

当时没想出什么好的点子，只觉得这里面最核心问题是要尽可能让自己占便宜，让对方吃亏。总结来说就是，打得过就打，打不过就拿自己的垃圾和对方的精锐互换。

不过，我一直没具体把这个思路实现出来，直到最近刷到力扣第 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 分就能过的话，何必考 90 分？每多考一分就亏一分，刚刚好卡在 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)。

至此，这道田忌赛马的题就解决了，其代码实现上用到了双指针技巧，从最快的马开始，比得过就比，比不过就送，这样就能对任意数量的马求取一个最优的比赛策略