单调对-协调

Question

我刚刚在Codity遇到了一个任务，我找不到目标O（n）效率的解决方案；我的解决方案运行为O（n2）。如果有人能给我一个提示，告诉我如何让它运行得更快，我会非常高兴。这是任务。

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

monotonic_pair是一对整数 （P， Q），使得 0 ≤ P ≤ Q

目标是找到指数相距最远的monotonic_pair。更准确地说，我们应该最大化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

还有另一种算法，基于查找对之间的最大距离（抱歉，PHP），它也具有O（n2）复杂度：

function solution($a) {

    $length = count($a);

    for($max = $length-1; $max > 0; $max-- ) {
        for($i = 0; $i < $length - $max ; $i++) {
            if ($a[$i] <= $a[$i+$max]) {
                return $max;
            }    
        }
    }

    return 0;
}

Answer 2

创建一个临时数组，其中包含按降序排列的最大值：

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 find(int[] t, int min) {
    int s = 0;
    int e = t.length-1;

    if (t[e] >= min) return e;

    while (true) {
        int x = (s+e) / 2;
        if (x == t.length-1) return t.length-1;
        if (t[x] >= min && t[x+1] < min) return x;

        if (t[x] < min) e = x;
        else s = x;
    }
}

你得到了一个解决方案:

int best = 0;
for (int i=0; i<A.length; i++) {
    int c = find(top, A[i]) - i;
    if (c > best) best = c;
    if (best >= A.length-i) return best;
}

return best;

Answer 3

马辛勒的比n^2的好，但仍在伦敦运行。您可以通过不每次都进行登录查询来进行优化。相反，同时向前迭代max数组和输入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;