找出数组中两个数字之间的最大落差.这个代码的时间复杂度是多少

Question

我有一个充满数字的数组。我需要找到两个数字之间的最大差值，但最大的数字在数组中最小的数字之前。

public static int maximalDrop(int[] a)例如：

对于阵列5, 21, 3, 27, 12, 24, 7, 6, 4，结果将是23 (27 - 4)

对于阵列5, 21, 3, 22, 12, 7, 26, 14，结果将是18 (21 - 3)

我想我是用时间复杂度O(N)写的，我的代码可以吗？我的代码的时间复杂性是多少？这是我写的方法：

public static int maximalDrop(int[] a) {
int i = 0;
int temp = 0;
int result = -1;
int k = a.length - 1;
boolean finishCheckLoop = false;
while (k > i) {
if (a[i] < a[i + 1] || finishCheckLoop == true) {
i++;
finishCheckLoop = false;
} else if (a[i] >= a[k] || a[i] <= a[k]) {
if (a[k] < 0)
temp = Math.abs(a[k]) + a[i];
else if (a[k] > 0)
temp = a[i] - a[k];
result = Math.max(temp, result);
k--;
}
if (i == k) {
k = a.length - 1;
finishCheckLoop = true;
}
}
return result;
}

Answer 1

您的代码似乎是O(N)，但对于任务来说相当复杂。

一个更简单(更快(的版本：

public static int maximalDrop(int[] a) {
int maxDrop = 0;
int drop = 0;
int max = Integer.MIN_VALUE;
int cur;
for (int i = 0; i < a.length; i++) {
cur = a[i];
if (cur > max) {
max = cur;
}
drop = max - cur;
if (drop > maxDrop) {
maxDrop = drop;
}
}
return maxDrop;
}

免责声明，我不是真正写java的，所以我不确定Integer.MIN_VALUE是否正确。

Answer 2

是的，您的代码具有O(N)的时间复杂性，但它不可读，可能很难编写。

几乎我们所有人都有这种不好的倾向，在知道如何解决问题之前就开始编码。这里提供的代码似乎是这种技术的产物。

为了改进代码，我们应该拿起纸笔，简单思考。注意，我们需要从左到右返回最大落差，因此有相当多的情况是

让我们保留high、low和maximalDrop变量：

• 当前数字创下新低：

  1. low=当前编号
  2. 如有必要，更新maximalDrop

• 目前的数字是一个新高——之前的低点无关紧要。

• 否则——什么都不做。

现在很容易编码：

public static int maximalDrop(int[] a) {
if (a.length == 0) {
return -1;
}
int h = a[0], l = a[0];
int maxDrop = -1;
for (int curr : a) {
if (curr < l) {
l = curr;
maxDrop = Math.max(h - l, maxDrop);
} else if (curr > h) {
h = curr;
l = Integer.MAX_VALUE;
}
}
return maxDrop;
}

输出示例：

System.out.println(maximalDrop(new int[]{5, 21, 3, 27, 12, 24, 7, 6, 4})); // 23
System.out.println(maximalDrop(new int[]{5, 21, 3, 22, 12, 7, 26, 14}));  // 18 
System.out.println(maximalDrop(new int[]{5, 6}));  // -1