1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
private int modulo = 1000000007;
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
List<int[]> engineers = new ArrayList<>();
for (int i = 0; i < speed.length; i++) {
engineers.add(new int[] { efficiency[i], speed[i] });
}
Collections.sort(engineers, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
long ans = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && engineers.get(i)[0] == engineers.get(i - 1)[0])
continue;
PriorityQueue<int[]> candidates = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (int j = i + 1; j < n; j++) {
candidates.offer(engineers.get(j));
if (candidates.size() == k) {
candidates.poll();
}
}
long speedSum = engineers.get(i)[1];
while (!candidates.isEmpty()) {
speedSum += candidates.poll()[1];
}
long currPerfor = speedSum * engineers.get(i)[0];
ans = Math.max(ans, currPerfor);
}
return (int) (ans % modulo);
}
}
|
这个想法是对的, 但是需要改进一些些. 就是穷举, 让每一个engineer都成为efficiency最小的那个, 看这种情况下最大的perf是多少. 然后让每一个engineer当一遍, 这样就能取到最大值了.
试着按照efficiency由大到小排序. 如果从小到大, 我们每次都要往后遍历到头然后找出k - 1个合适的人选. 如果从大到小, 那么我们可以把之前存在PQ中的候选人留着, 这样能够重复利用之前的计算.
这个时间复杂度就很高了第一个iteration是(n - 1)log(n - 1), 然后是(n - 2)log(n - 2)….
空间复杂度: O(n) 因为用了PQ和engineers这个list.
看看下面的方法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
private int modulo = 1000000007;
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
List<int[]> engineers = new ArrayList<>();
for (int i = 0; i < speed.length; i++) {
engineers.add(new int[] { efficiency[i], speed[i] });
}
Collections.sort(engineers, (a, b) -> b[0] - a[0]);
long ans = 0;
long currSpeed = 0;
PriorityQueue<int[]> candidates = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (int i = 0; i < n; i++) {
if (candidates.size() == k) {
currSpeed -= candidates.poll()[1];
}
candidates.offer(engineers.get(i));
currSpeed += engineers.get(i)[1];
long currEfficiency = engineers.get(i)[0];
long currPerf = currSpeed * currEfficiency;
ans = Math.max(ans, currPerf);
}
return (int) (ans % modulo);
}
}
|
需要注意的是, 我们始终记录PQ中所有engineers的speed sum是多少.
时间复杂度: O(nlogn + nlogk) nlogn是开始的时候sort了一下, 一次之后每次都对PQ进行操作.
空间复杂度: O(n) 用了engineers这个list以及PQ.
