8

我有一个算法问题：

给定一个大小为 N 的数组（假设所有元素都是整数），找到最大的下降（不一定是连续的）： max{array[i]-array[j]} 有一个约束： i>j 。

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

我认为一个改进的解决方案是首先映射数组的索引，对数组进行排序并通过数组找到最大的下降。这个复杂度是 O(nlogn)。

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

PS：我曾经想过一个线性的解决方案：创建两个额外的数组，一个是记录给定数组从头到尾的最大值，另一个是从尾到头的最小值。然后，通过两个数组一通。但是，有人认为这不正确并且占用了太大的空间。所以我想知道一个更好的解决方案。——李娟流

4

5 回答 5

5

您需要跟踪两件事：

您似乎与元素 i 相关的最大数量，以及相对于最大数量（即 i 之前的最大数量，减去元素 i）的最大下降。这将是时间上的 O(n) 和空间上的 O(1)。

这个问题正是“股票买卖”的面试题，解决方法可以在这里找到：最大单笔卖出利润

于 2013-02-22T08:41:53.877 回答
5

没有额外空间的 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;
}
于 2015-08-22T22:33:56.840 回答
4

创建新的 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).

正确性证明（指南）：

让最大的下降是从 indexi到 index 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>k这样max[k]=arr[u], min[k]=arr[v]，你得到那个，这与最大下降arr[u] - arr[v] > arr[i] - arr[j]的事实相矛盾。i,j

量子点

于 2013-02-22T08:42:52.457 回答
-1

我只能想到 O(nlogn) 但这一个即使相同的复杂性应该比排序和找到最大的下降更快。

您可以做的是计算 O(n) 中连续数字的差异，然后问题将简化为找到连续子数组的 MAX(sum)，即 O(nlogn)

于 2013-02-22T08:38:49.197 回答
-1 
public static int maxDrop(int[]array){

    int maxDrop =0,drop=0,min=array[0];

    for(int i=1;i<array.length;i++){

        if(array[i]<min){
            min=array[i];
        }

        drop = array[i]-min;

        if(drop>maxDrop){
            maxDrop=drop;
        }

    }

    System.out.println(maxDrop);
    return maxDrop;

}
于 2014-07-15T11:09:15.057 回答