在O(n)的时间复杂度内，找到一个未排序数组中满足 j>i 的最大 A[j] - A[i] 值。

Question

这是一个亚马逊的面试题。我已经使用动态规划以O(n)的时间复杂度解决了这个问题。但我想知道是否有比O(n)更优化的方法。

例如，假设下面是数组：

3 7 1 4 2 4 returns 4

5 4 3 2 1 returns Nothing

4 3 2 2 3 returns 1

这是我编写的代码Code

- Algorithmist

---

从O(n)到O(n log n)我不明白如何会是一种优化。 - aioobe

但是O(nlogn)比O(n)更糟糕... - Daniel Kamil Kozar

你说你已经有了一个O(n)的解决方案。根据定义，任何O(n)也是O(n logn)。 - NPE

抱歉，你不能成为算法工程师 :-( - DhruvPathak

这里比O(n)更好吗？我认为你至少要检查每个元素一次，特别是考虑到示例数组是未排序的。 - gorlum0

Answer 1

假设你有一个int A[N]。

int res = -1;
int min_value = A[0];
for(int i=1; i<N; i++) {
    // A[i] - A[j] is maximal, when A[j] is minimal value from {A[0], A[1],.., A[i-1]}
    res = max(res, A[i] - min_value);
    min_value = min(min_value, A[i]);
}
return res;

时间复杂度为O(N)。

需要检查N个元素，因此O（N）是最好的结果。

- Jarosław Gomułka

---

你的意思是 = min(min_value, A[i]) 吗？ - BlackJack

@Algorithmist，不知道为什么这看起来非常像这个问题，它来自于一个正在进行中的比赛。> . < - Priyank Bhatnagar

Answer 2

但我想知道是否有比O(n)更高效的优化方法。

任何一个n个元素都可能成为解的一部分，因此每个元素都需要被检查。因此，O(n)是无法改进的。

为了完整起见，这里提供一种需要O(n)时间且只需要O(1)内存的解决方案：

A = [1, 10, 20, -10, 3, 4, 18, 42, 15]

smallest = A[0]
maxdiff = float('-inf')
for x in A[1:]:
  maxdiff = max(maxdiff, x - smallest)
  smallest = min(smallest, x)
print maxdiff

- NPE

---

对于打字错误我很抱歉...我同时在解决另一个问题，然后它们混淆了。 - Algorithmist

@Algorithmist：不，你不能比O(n)更好。任何元素都可能是解决方案的一部分，因此需要进行检查。有O(n)个元素。 - NPE

Answer 3

无论采用何种方法，您都必须至少遍历一次数组，这一步本身就是O(n)，因此无法比O(n)更好。剩下的任务只是尽量减小常数。

- MoveFast

Answer 4

public static int maxOrderedDiff(int[] A){
    //A[x]-A[y] | x>y
    int min = 0, max = 0;
    int less = 0;
    for(int i=1; i<A.length; i++){
        if(A[less]>A[i]){
            less = i;
        }
        if(A[i]-A[min]>A[max]-A[min] || A[i]-A[less] >A[max]-A[min]){
            max=i;
            if(A[less]<A[min])
                min = less;
        }
    }

    return max>min? A[max]-A[min]: -1;
}//maxOrderedDiff

测试使用：

public static void main(String[] args){
    int[][] A = {{3, 7, 1, 4, 2, 4},{5, 4, 3, 2,1},{4, 3, 2, 2, 3}};

    for(int[] B: A)
        System.out.format("%s :: %d%n", Arrays.toString(B), maxOrderedDiff(B));
}

- kasavbere