java - 查找数组中可能存在的最大差异，其中较小的整数较早出现

Question

这是一道面试题:

找出整数数组中可能存在的最大差异，使得较小的整数出现在数组中的较早位置。

约束:数字不是唯一的。范围是java的Integer范围。 (或任何其他语言)

例子:

输入 1:{1, 100, 2, 105, -10, 30, 100}

最大的差异在-10和100之间-> 110(这里-10在第5个索引处，100在第7个索引处)

输入 2:{1, 100, 2, 105, -10, 30, 80}

最大的区别是在 1 和 105 之间 -> 104(这里 1 在第 1 个索引处，105 在第 4 个索引处)

可能的解决方案:

一种方法是检查所有可能的差异并跟踪迄今为止发现的最大差异 O(n^2) 复杂度。

这能在比 O(n^2) 更短的时间内完成吗？

Answer 1

Dhandeep 的算法很好，Vivek 将代码翻译成 Java 也很有效!此外，我们还可以正常而不是反向扫描数组:

int seed[] = {1, 100, 2, 105, -10, 30, 100};
int maxDiff=Integer.MIN_VALUE, minNumber = Integer.MAX_VALUE;

for (int i = 0; i < seed.length ; i++){
    if(minNumber > seed[i]) 
       minNumber = seed[i];

    maxDiff = Math.max(maxDiff, (seed[i]-minNumber));
}
System.out.println(maxDiff);