找到数组中最大丢落的算法

Question

我有一个算法问题:

给定大小为N的数组(假设所有元素都是整数),找到最大的drop(不一定是连续的):max {array [i] -array [j]},其约束为:i> j.

简单的解决方案是两个循环并遍历i和j的所有可能值,但时间复杂度为O(n*n).

我认为一个改进的解决方案是首先映射数组的索引,对数组进行排序,然后遍历数组以找到最大的丢弃.这种复杂性是O(nlogn).

有线性时间复杂度的解决方案吗？如何？

PS:我曾经想过一个线性解决方案:创建两个额外的数组,一个是从开始到结束记录给定数组的最大值,另一个是从结尾到开始的最小值.然后,通过两个阵列一通.然而,有人认为不正确并占用太大的空间.所以我想知道一个更好的解决方案. - lijuanliu

Answer 1

没有额外空间的 O(n) 解：

public int maxDrop(int[] a) {
    int max = a[0];
    int maxDrop = -1;
    for (int i = 0; i < a.length; i++) {
        if (max < a[i]) {
            max = a[i];
        }
        else {
            int drop = max - a[i];
            maxDrop = Math.max(maxDrop, drop);
        }
    }
    return maxDrop;
}

Answer 2

你需要跟踪两件事:

您拥有的最大数量似乎是元素i,并且相对于最大数字(即i之前的最大数量减去元素i),您的最大数量下降.这将是O(n)的时间和O(1)的空间.

这个问题正是"股票买/卖"面试问题,解决方案可以在这里找到:最大单卖利润

Answer 3

创建新的2个数组：

max[i] = max { arr[0], arr[1], ..., arr[i] }
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] }
(max is the maximum from first to i, min is the minimum from i to last)

现在，迭代辅助数组并找到最大差异max[i] - min[i]

这总共需要 3 次迭代，因此O(n).

正确性证明（指南）：

让最大的下降是从索引i到索引j，其中i<j：

1. 然后，max[i] >= arr[j]（因为我们已经通过了它），并且 min[i] <= arr[i]- 因此max[j] - min[j] >= arr[i] - arr[j]，算法提供的答案至少与最优答案一样好。
2. 另外，由于最大的跌幅是i,j，因此不可能有k<j 这样的arr[k] < arr[i]，因为这样最大的跌幅将是从arr[k]到arr[j]。相似 - 出于同样的原因，不可能存在k>j这样的 arr[k] < arr[j]- 因此max[j]-min[j] <= arr[i] - arr[j]

由以上我们可以得出结论max[j]-min[j] = arr[i] - arr[j]。剩下的就是正式完整的证明，证明对于每个k你得到的max[k]-min[k] <= max[j] - min[j]， 确实是这样，否则有一些，u<k这样，你得到那个，这与最大下降的事实相矛盾。v>kmax[k]=arr[u], min[k]=arr[v]arr[u] - arr[v] > arr[i] - arr[j]i,j

量子电动力学