forked from charles-wangkai/codility
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cannonballs.java
36 lines (31 loc) · 824 Bytes
/
Cannonballs.java
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
31
32
33
34
35
36
import java.util.Arrays;
public class Cannonballs {
public int[] solution(int[] A, int[] B) {
int maxCannon = -1;
for (int cannon : B) {
maxCannon = Math.max(maxCannon, cannon);
}
int[] hitIndices = new int[maxCannon + 1];
Arrays.fill(hitIndices, Integer.MAX_VALUE);
int prevHeight = -1;
for (int i = 0; i < A.length; i++) {
if (A[i] > prevHeight) {
for (int j = prevHeight + 1; j <= A[i] && j < hitIndices.length; j++) {
hitIndices[j] = i;
}
prevHeight = A[i];
}
}
int[] A1 = Arrays.copyOf(A, A.length);
for (int cannon : B) {
int hitIndex = hitIndices[cannon];
if (hitIndex == 0 || hitIndex >= A.length) {
continue;
}
A1[hitIndex - 1]++;
hitIndices[A1[hitIndex - 1]] = Math.min(
hitIndices[A1[hitIndex - 1]], hitIndex - 1);
}
return A1;
}
}