使用较早出现的较小整数查找数组中可能存在的最大差异

Question

这是一个面试问题:

找到整数数组中可能存在的最大差异,以便较小的整数出现在数组的较早位置.

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

例:

输入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);

Answer 2

从最后一个元素开始并向后移动.记住迄今为止发生的最大元素.对于每个元素从最大值中减去并存储在相应位置.

此外,您可以保留一个元素来存储最大差异并直接输出.O(n)时间,O(1)空间.

int max = INT_MIN;
int maxdiff = 0;

for (i = sizeof(arr) / sizeof(int) - 1; i >= 0; i--) {
  if (max < arr[i]) {
    max = arr[i];
  }
  int diff = max - arr[i];
  if (maxdiff < diff) {
    maxdiff = diff;
  }
}

print maxdiff;