时间戳

首页 > 解决方案 > 数组中的最大差异未通过 HackerRank 中的所有测试用例

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

问题描述

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

给出一个整数数组，计算所有可能对的任何项目和任何较低索引的较小项目之间的最大差异。换句话说，对于数组，找到所有 i、j和arr的最大值。如果没有项目具有较低索引的较小项目，则返回。arr[j] - arr[i]0 <= i < j < narr[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]]：：整数数组。

约束

解决方案

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）

标签： arraysalgorithmperformancekotlin

解决方案

正如@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值就可以让我们走上正确的道路，因为会arr[i]比 current 少几个arr[j]，但是在所有之前i的 current中取最小值arr[j]显然会给我们最大的差异。

推荐阅读