效率:整数数组的一个子集中两个项之间的最大差值

Question

我参加了一次编程考试，任务是为特定问题编写高效的代码。我相信我得到了正确的答案（它适用于5个测试场景中的3个），但其余两个测试场景（我没有详细信息）由于耗时超过2秒而失败。

我用.slice和.apply()克隆了一个子数组，并得到了其中的max/min值。这是最慢的部分吗？我可以做些什么来改进它？

我的代码：

function find_deviation(v, d) {
    var maxMedian = 0;
    var i = 0;
    var len = v.length - d + 1;
    var sequence, min, max, median;
    for(;i < len; ++i) {
        sequence = v.slice(i, i+d);
        min = Math.min.apply(null, sequence);
        max = Math.max.apply(null, sequence);
        median = max - min;
        if(median > maxMedian) {
            maxMedian = median;
        }
    }
    console.log(maxMedian);
}

问题：

长度为d个项目的数组v的子集中的两个项目之间的最大差值（maxMedian）是多少？v数组中的所有项都是整数，d也是整数。

Answer 1

首先，我假设你想在d大小的所有紧凑子阵列之间找到最大差异，这是对的吗？

如果是这样的话，那么从我的头顶上我可以看到两个问题：

• 阵列切片的开销
• Math.min和Math.max的复杂度是O（n），当你同时执行这两个运算时，它会生成O（2n）

为了解决这两个问题，我提出了以下建议：

function find_deviation(v, d) {
    var maxDifferenceGlobal = 0;
    var len = v.length - d + 1;
    for(var i = 0; i < len; ++i) {
        var min, max;
        if (v[i] <= v[i + 1]) {
            min = v[i]; max = v[i + 1];
        } else {
            max = v[i]; min = v[i + 1];
        }
        for(var j = i + 2; j < i + d; ++j) {
            if (min > v[j]) { min = v[j]; }
            if (max < v[j]) { max = v[j]; }
        }
        var maxDifferenceLocal = Math.abs(max - min);
        if(maxDifferenceLocal > maxDifferenceGlobal) {
            maxDifferenceGlobal = maxDifferenceLocal;
        }
    }
    console.log(maxDifferenceGlobal);
}

这消除了阵列切片的开销，并在O（n）中找到了max和min，因此仅通过常数更好，但会产生的差异。此外，您不应该使用Math.abs来计算差异吗？