本文涉及LeetCode 870. 优势洗牌

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]
示例 2：

输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

这就像⽥忌赛⻢的情景，nums1 就是⽥忌的⻢，nums2 就是⻬王的⻢，数组中的元素就是⻢的战⽃⼒：

算法策略是：将⻬王和⽥忌的⻢按照战⽃⼒排序，然后按照排名⼀⼀对⽐。如果⽥忌的⻢能赢，那就⽐赛，如果赢不了，那就换个垫底的来送⼈头，保存实⼒。

这里要注意一个问题：是否需要保存实力，即如果⽥忌的⼆号选⼿也能⼲得过⻬王的⼀号选⼿，此时让⼆号选⼿去对决⻬王的⼀号选⼿，不是更节约？

这种节约的策略是没问题的，但是没有必要。

我们暂且把⽥忌的⼀号选⼿称为 T1，⼆号选⼿称为 T2，⻬王的⼀号选⼿称为 Q1。如果 T2 能赢 Q1，你试图保存⼰⽅实⼒，让 T2 去战 Q1，把 T1 留着是为了对付谁？显然，你担⼼⻬王还有战⼒⼤于 T2 的⻢，可以让 T1 去对付。但是你仔细想想，现在 T2 已经是可以战胜 Q1 的，Q1 可是⻬王的最快的⻢，⻬王剩下的那些⻢⾥，怎么可能还有⽐ T2 更强的⻢？

所以没必要节约。

根据上述思路得到的代码逻辑如下：

对两个数组nums1和nums2排序
对两个数组的元素挨个比较，如果nums1[i]>nums2[i]那就比，否则就换上nums1最小的元素进行比较。

由于需要对两个数组排序，但是返回结果依赖nums2的顺序，所以不能直接对nums2进行排序，而是利用优先级队列。（将(index, nums2[index]放入优先级队列，出队优先级按照nums2[index]大小，index记录索引值）

此外，解法还是用到双指针技巧。完整代码如下。

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 {
            // 否则用最小值去换nums2的最大值
            res[i] = nums1[left];
            left++;
        }
    }
    return res;
}

参考资料

labuladong: 算法大师——孙膑