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

Question

我申请了一份工作，准雇主给我发了下面的HackerRank问题，在公共(public)区域找不到。

给定一个整数数组，计算所有可能对的任何项目与任何较低索引的较小项目之间的最大差异。换句话说，对于数组 arr , 求 arr[j] - arr[i] 的最大值对于所有 i, j，其中 0 <= i < j < n和 arr[i] < arr[j] .如果没有项目具有索引较低的较小项目，则返回 -1 .

例如，给定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]] : 整数数组。

约束

• 1 <= n <= 2*10^5
• -10^6 <= arr[i] <= 10^6 其中 [0, 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

如 this answer 中所述@Tom 关于失败的测试，我觉得你的解决方案相当复杂，因为你试图保持一对。我已将其简化如下(不是 kotlin dev，所以下面是 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);

• 嗯，条件是说0 <= i < j < n和 arr[i] < arr[j] .这需要一种贪婪的方法，它指向我们只需要维护 min 的事实。当我们在数组中从左向右移动时的值。

• 只是维护 min value 将我们带入正确的路径，因为会有多个 arr[i]小于当前 arr[j] , 但在所有以前的 i 中取最小值当前 arr[j]显然会给我们最大的差异。