题目大意：
最大的团队表现值
公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。
团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
示例 1：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 输出：60 解释： 我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
示例 2：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3 输出：68 解释： 此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
示例 3：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72
提示：
- 1 <= n <= 10^5
- speed.length == n
- efficiency.length == n
- 1 <= speed[i] <= 10^5
- 1 <= efficiency[i] <= 10^8
- 1 <= k <= n
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1383
解题思路分析：
我们先将题目给出的两个数组合并成一个二维数组item[][]，item[i][0]代表第i个程序猿的速度，item[i][1]代表第i个程序员的效率。然后再对这个二维数组按照效率由高到低的顺序进行排序。
item数组构建完成后，还需建立一个PriorityQueue用来动态保存当前速度最快的k个人。我们开始循环item数组，如果 PriorityQueue 的size小于k，我们向Queue中加入当前程序猿的速度。如果 PriorityQueue 的size等于k，那么我们先从Queue中取出一个速度最慢的，然后再将当前速度加入。由于item数组是按照效率降序排序的，因此新加入到Queue中的元素相对应的效率一定是Queue中最低的，换句话说，每当我们更换一个Queue中的元素，Queue中的元素对应的效率最小值会被更新，而Queue中所有元素的速度和可能会增大。即乘法的两个乘数，一个变小，另一个可能变大，他们的乘积会变大或是变小，我们需要通过计算来得知，因此，每一步循环，我们都应该使用Queue中元素的速度和乘以当前插入元素的效率得到一个当前结果，并用该结果更新全局的最大值，直到循环结束，我们也就得到了全局最大值。
实现代码：
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
// 将两个一维数组合并为一个二维数组
int[][] items = new int[n][2];
for(int i=0;i<n;i++){
items[i][0]=speed[i];
items[i][1]=efficiency[i];
}
// 数组按照效率由大到小排序
Arrays.sort(items,(a,b)->b[1]-a[1]);
// 返回结果
long max=0;
// 当前速度和
long sum=0;
PriorityQueue<Integer> q=new PriorityQueue<>();
for(int i=0;i<n;i++){
// 如果queue的元素个数等于k
if(q.size()==k){
// 从queue中取出一个速度最慢的
// 更新当前Queue中的速度和
sum-=q.poll();
}
// 将当前元素的速度加入到Queue
q.offer(items[i][0]);
// 更新当前Queue中的速度和
sum+=items[i][0];
// 计算当前Queue中元素的速度乘以效率
long res=sum*items[i][1];
// 更新全局最大值
max=Math.max(res, max);
}
return (int)(max%1000000007);
} 本题解法执行时间为40ms。
Runtime: 40 ms, faster than 50.00% of Java online submissions for Maximum Performance of a Team.
Memory Usage: 57.2 MB, less than 100.00% of Java online submissions for Maximum Performance of a Team.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1383-maximum-performance-of-a-team-解题思路分析/