题解 | #最高售价的两只牛#

知识点：优先队列

思路：一开始的思路：a里面选最大，b里面找最大， 做到不重复，但是时间复杂度是o（n）3；

其实模拟我们选取操作的时候，无非就是先选择a数组里最大的，然后带着这个值去b数组里找

1.sum和最大

2.sum和一致，a最大又因为，b数组是排序好的，那么我们就不需要找了，直接从后往前取即可；

最后选取完的值，移除或者做标记，做到不重复。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pricesA int整型一维数组
     * @param pricesB int整型一维数组
     * @param k int整型
     * @return int整型二维数组
     */

    static class Struct {
        int a, b, sum;
        Struct(int a, int b, int sum) {
            this.a = a;
            this.b = b;
            this.sum = sum;
        }
    }
    public int[][] kPairsWithLargestSums (int[] pricesA, int[] pricesB, int k) {
        // write code here
        //定义该优先队列规则，售价优先，售价一致，A组优先
        PriorityQueue<Struct> queue = new PriorityQueue<>( (a,b) ->{
            if(a.sum == b.sum) return pricesA[b.a] - pricesA[a.a];
            return b.sum - a.sum;
        });

        int indexA =pricesA.length;int indexB =pricesB.length;
        for (int i=0;i<indexA;i++){
            queue.add(new Struct(i,indexB-1,pricesA[i] + pricesB[indexB-1]));
        }
        ArrayList<int[]> arr = new ArrayList<>();
        while (k-- >0 && !queue.isEmpty()){
            Struct res = queue.poll();//每次取出肯定是满足条件的最大值
            arr.add(new int[]{pricesA[res.a],pricesB[res.b]});
            //维护队列
            if(res.b >0){
                res.b--;
                res.sum = pricesA[res.a]+ pricesB[res.b];
                queue.add(res);
            }
        }
        return arr.toArray(new int[0][]);
    }
}