未通过HackerRank中所有测试用例的数组中的最大差异

Question

我申请了一份工作，未来的雇主给我发了以下黑客问题，在公共场所找不到。

给出一个整数数组，计算所有可能对的任何项和任何索引较低的较小项之间的最大差值。换句话说，对于数组arr，查找所有i，j的arr[j]-arr[i]的最大值，其中0

例如，给定arr=[1,2,6,4]，首先将2与其左侧的元素进行比较。1较小，因此计算差值2-1=1。6大于2和1，因此计算差值6-2=4和6-1=5。最后一个元素4只大于2和1，差别是4-2=2和4-1=3。最大的差异是6-1=5。

功能描述

完成函数maxDifference。函数必须返回一个整数，该整数表示arr中的最大差值。

maxDifference具有以下参数：arr[arr[0]，arr[1]，。。。arr[n-1]：整数数组。

约束条件

• 一,

解决方案

fun maxDifference(arr: Array<Int>): Int {

    var min: Pair<Int, Int> = Pair(0, 0)
    var max: Pair<Int, Int> = Pair(0, 0)
    var result = -1

    for(i in 0 until arr.size) {
        when {
            i == 0 -> {
                min = Pair(i, arr[i])
                max = Pair(i, arr[i])
            }
            min.second > arr[i] -> min = Pair(i, arr[i])
            max.second < arr[i] -> max = Pair(i, arr[i])
        }

        if(max.first > min.first && max.second > min.second)
            result = kotlin.math.max(result, max.second - min.second)
    }

    return result
}

问题所在

由于某种原因，上述解决方案无法通过HackerRank中的所有测试用例。不幸的是，发送此测试的雇主不愿意透露测试用例，以了解问题所在。代码本身工作正常。

测试用例

1. [2,3,10,2,4,8,1]-（预期结果为8）
2. [7,9,5,6,3,2]-（预期结果为2）
3. [3]-（预期结果为-1）
4. [-3，-2]-（预期结果为1）




Answer 1

试试这个：

fun maxiDiff(numbers:List<Int>):Int{
    
    val numbersSorted = numbers.distinct().sorted()
    
    if(numbersSorted.isEmpty() || numbersSorted.size == 1)return -1
    
    val gaps = numbersSorted.zipWithNext{a,b -> Math.abs(b-a)}
    
    return gaps.max() ?: -1
}

Answer 2

您的初始值是错误的-您应该将最小值/最大值硬编码为±10⁶
而且最小值/最大值不是没有用吗？您不应该使用最小/最大差异吗
这里的示例应该是4-3=1，但找不到（假设您的代码的工作方式与此完全相同）：

js prettyprint-override">function maxDifference(arr) {
    var min = [0,0];
    var max = [0,0];
    var result = -1

    for(var i in arr) {
        if(i == 0) {
            min = [i, arr[i]];
            max = [i, arr[i]];
        }
        if(min[1] > arr[i]) min = [i, arr[i]];
        if(max[1] < arr[i]) max = [i, arr[i]];

        if(max[0] > min[0] && max[1] > min[1])
            result = Math.max(result, max[1] - min[1])
    }

    return result
}
var a = prompt("Enter data:","9,7,5,6,3,4");
console.log("Array:",a);
console.log(maxDifference(a.split(',')));

Answer 3

正如@Tom在这个关于测试失败的回答中已经提到的，我觉得你的解决方案相当复杂，因为你试图维护一对。我将其简化如下（不是kotlin开发人员，所以下面是Javascript）：

var arr = [1, 2, 6, 4];

var min = arr[0];
var diff = -1;

for (var i = 1; i < arr.length; ++i) {
  if (arr[i] > min) diff = Math.max(arr[i] - min, diff);
  min = Math.min(min, arr[i]);
}

console.log(diff);