我试图用嵌套的for循环来解决Codility样本测试,但是它的表现还不够好。然后,我尝试了以下解决方案,并且工作正常。但是我对第二个解决方案中第二个for循环的工作方式一无所知。
第一个解决方案没有足够的性能。 https://app.codility.com/demo/results/training5Z4ZB8-385/
第二种解决方案是正确的,具有良好的性能。 https://app.codility.com/demo/results/training4E8QZS-MQK/。
public class Solution5 {
public int[] solution(int N, int[] A) {
int[] counter = new int[N];
int maxUpdate = 0, I, B = 0;
for (int i = 0; i < A.length; i++) {
I = A[i] - 1;
if (A[i] >= 1 && A[i] <= N) {
counter[I] = Math.max(B,counter[I]) + 1;
maxUpdate = Math.max(maxUpdate, counter[I]);
} else if (A[i] == (N + 1)) {
B = maxUpdate;
}
}
for (int i = 0; i < counter.length; i++) {
counter[i] = Math.max(B, counter[i]);
}
return counter;
}
}
想法是将最大计数器操作推迟到最后。您可能已经注意到,在没有首先使用B
计算最大值的情况下,永远不会使用计数器的值,并且B
是最后一次在maxUpdate
中找到N+1
时的最大值(A
) 。 maxUpdate
始终包含计数器数组中的最大值:与所有计数器一样,它从零开始,并且每增加一个计数器,maxUpdate
就会更新。