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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pricesA int整型一维数组 
     * @param pricesB int整型一维数组 
     * @param k int整型 
     * @return int整型二维数组
     */
  
  	/**
	 * 创建结点,用于存放下标和累加值
	 * 建立大根堆
  	 */
    static class Node{
        int a,b,sum;
        Node(int a,int b,int sum){
            this.a = a;
            this.b = b;
            this.sum = sum;
        }
    }

    public int[][] kPairsWithLargestSums (int[] pricesA, int[] pricesB, int k) {
	  //优先队列
        PriorityQueue<Node> que = new PriorityQueue<Node>((a, b)->{
            //售价一致时,A组优先
            if(b.sum==a.sum) return pricesA[b.a]-pricesA[a.a];
		  //售价最高优先
            return b.sum-a.sum;});
        int m = pricesA.length,n=pricesB.length;
	  //首先将A所有值和B组最大值组合,入堆,
	  //此时得到的堆一定是各个以A优先组合的最大值
        for(int i=0;i<m;i++){
            que.add(new Node(i,n-1,pricesA[i]+pricesB[n-1]));
        }
        ArrayList<List<Integer>> res = new ArrayList<>();
        while(k-->0 && !que.isEmpty()){
            Node t = que.poll();;
            // System.out.println(Arrays.asList(pricesA[t.a],pricesB[t.b]));
		  //取堆顶最大值进入结果集
            res.add(Arrays.asList(pricesA[t.a],pricesB[t.b]));
            if(t.b>0){
			  //取出B组下标向前移动1
                t.b--;
                t.sum = pricesA[t.a]+pricesB[t.b];
			  //入堆,此节点必然小于先前结点,入堆后由先前定义的compare维护
                que.add(t);
            }
        }
	  //转换为int[][]
        int l =  res.size();
        int[][] result = new int[l][2];
        for(int i=0;i<l;i++){
            for(int j=0;j<2;j++){
                result[i][j] = res.get(i).get(j);
                
            }
        }
        return result;
    }
}