X

LEETCODE 1383. Maximum Performance of a Team 解题思路分析

题目大意:

最大的团队表现值

公司有编号为 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-解题思路分析/
Categories: leetcode
kwantong: