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

import java.util.*;


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

        Node(int _ax, int _bx, int _sum) {
            ax = _ax;
            bx = _bx;
            sum = _sum;
        }
    }

    public int[][] kPairsWithLargestSums(int[] pricesA, int[] pricesB, int k) {
        List<int[]> res = new ArrayList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>((left, right) -> {
            if (left.sum == right.sum) {
                return Integer.compare(right.ax, left.ax);
            }
            return Integer.compare(right.sum, left.sum);
        });

        for (int i = 0; i < pricesA.length; i++) {
            pq.offer(new Node(i, pricesB.length - 1,
                              pricesA[i] + pricesB[pricesB.length - 1]));
        }

        while (!pq.isEmpty() && k > 0) {
            Node n = pq.poll();
            res.add(new int[] {pricesA[n.ax], pricesB[n.bx]});
            if (n.bx > 0) {
                pq.offer(new Node(n.ax, n.bx - 1, pricesA[n.ax] + pricesB[n.bx - 1]));
            }
            k--;
        }

        int[][] result = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }

        return result;
    }
}

Java 编写

该题考察的知识点包括：

1. 优先队列
2. 自定义比较器
3. 堆

代码的文字解释：

函数的目标是找到两个数组中价格总和最大的 k 对牛，并返回这些牛对的价格组成的二维数组。在实现中，代码使用优先队列来维护可能的牛对的信息，使用自定义的比较器来定义比较规则。算法的思路是，首先将每个 A 牛与 B 牛的组合以及它们的价格总和加入优先队列，然后从队列中取出前 k 对价格总和最大的牛对，并将它们放入结果数组中返回。这样就能满足题目要求的价格总和降序排列，相同总和情况下优先考虑 A 牛的价格更高。