c++ - codility MaxDistanceMonotonic，我的解决方案有什么问题

Question

问题:

给定一个由 N 个整数组成的非空零索引数组 A。单调对是一对整数 (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) 中。

写一个函数:

整数解法( vector &A)；

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

例如，给定:

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)，超出输入存储(不包括输入参数所需的存储)。可以修改输入数组的元素。

这是我对 MaxDistanceMonotonic 的解决方案:

    int solution(vector<int> &A) {

    long int result;

    long int max = A.size() - 1;
    long int min = 0;

    while(A.at(max) < A.at(min)){
        max--;
        min++;
    }

    result = max - min;

    while(max < (long int)A.size()){
        while(min >= 0){
            if(A.at(max) >= A.at(min) && max - min > result){
                result = max - min;    
            }
        min--;
        }
    max++;
    }

    return result;
}

而我的结果是这样的，我上次测试的答案有什么问题:

Answer 1

如果你有:

0  1 2  3  4  5
31 2 10 11 12 30

您的算法输出 3，但正确答案是 4 = 5 - 1。

发生这种情况是因为您的 min 在内部 while 循环的第一次完整运行中变为 -1，因此 (1, 5) 对永远没有机会要检查，max 在进入嵌套 while 时从 4 开始。

请注意，问题描述需要 O(n) 额外的存储空间，而您使用的是 O(1)。我不认为用 O(1) 额外存储和 O(n) 时间来解决问题是不可能的。

我建议您重新考虑您的方法。放弃的话官方有解决办法here .