java - 单调对 - Codility

Question

我刚刚在 Codility，遇到了一个任务，我找不到目标 O(n) 效率的解决方案；我的解决方案运行时间为 O(n2)。如果有人能给我一些关于如何让它运行得更快的提示，我将非常高兴。这是任务。

给定一个由N个整数组成的非空零索引数组A。

monotonic_pair 是一对整数 (P, Q)，满足 0 ≤ P ≤ Q < N 且 A[P] ≤ A[Q]。

目标是找到索引相距最远的单调对。更准确地说，我们应该最大化 Q − P 的值。仅找到距离就足够了。

例如，考虑这样的数组 A:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

有十一个单调对:(0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。最大的距离是 3，在对 (1, 4) 中。

写一个函数:

class Solution { public int solution(int[] A);

给定一个包含 N 个整数的非空零索引数组 A，返回任何 monotonic_pairs 中的最大距离。

例如，给定:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

函数应该返回 3，如上所述。

假设:

N为[1..300,000]范围内的整数； 数组 A 的每个元素都是 [−1,000,000,000..1,000,000,000] 范围内的整数。 复杂性:

预期的最坏情况时间复杂度为 O(N)； 预期的最坏情况空间复杂度为 O(N)，超出输入存储(不包括输入参数所需的存储)。 可以修改输入数组的元素。

我的第一个想法解决方案(在 O(n2) 中运行):

    public static int solution(int[] A) {
    int max = 0;
    for(int i=0; i<A.length-1; i++) {
        for(int j=i+1; j<A.length; j++) {
            if(A[j] >= A[i] &&
                    (j - i) >= max) {
                max = j - i;
            }
        }
    }
    return max;
}

Answer 1

MarcinLe 的比 n^2 好，但仍然在 nlogn 中运行。您可以通过不每次都进行登录查找来进行优化。相反，同时向前迭代最大数组和输入 A[] 数组以保证线性时间。

int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
    if (A[i] > max) max = A[i];
    top[i] = max;
}

int best = 0;
int curMaxIndex = 0;
for (int i=0; i<A.length; i++) {
    while(curMaxIndex < top.length && top[curMaxIndex] >= A[i])
        curMaxIndex++;
    if((curMaxIndex - 1 - i) > best)
        best = curMaxIndex - 1 - i
}

return best;