leetcode870.优势洗牌

• 题目：给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

  返回 A 的任意排列，使其相对于 B 的优势最大化。

• 思路：优势洗牌类似于田忌赛马的策略，用数组A较差的牌匹配数组B最强的牌，从而得到相对于B的优势最大化；

• 首先将数组A进行升序排序；利用PriorityQueue大顶堆的方法使数组B进行降序排序且不改变原有的数组B的位置；

• 利用田忌赛马的策略返回结果数组res；

• • 定义left、right变量，当数组B中的最大值小于数组A下标为right的值时；将数组A下标为right的值赋给res数组，res数组的下标为数组B中的最大值的对应位置，right--；

  • 当数组B中的最大值大于数组A下标为right的值时；将数组A下标为left的值赋给res数组，res数组的下标为数组B中的最大值的对应位置；left++；

class Solution {
    public 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];//默认是小顶堆，这里改为了大顶堆
            }
        );
   
        int res[] = new int[n];

        for (int i = 0; i < n; i++) {
            maxpq.offer(new int[]{i, nums2[i]});
        //将0号元素nums2[0]纳入优先队列，然后是1号元素nums2[1]纳入优先队列...
            }
            //对数组A进行升序排序
        Arrays.sort(nums1);
        int left = 0;
        int right = n-1;
        while(!maxpq.isEmpty()){
            int[] tmp = maxpq.poll();
            // maxval 是 nums2 中的最大值，i 是对应索引
            int i = tmp[0];
            int maxval = tmp[1];
            
            if(maxval<nums1[right]){
                res[i] = nums1[right];
                right--;
            }else{
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }
}