查找数组中的最大差异

Question

我正在研究一种算法来返回任何一对数字的 差值， 使得这对数字中较大的整数出现在比较小的整数更高的索引处（在数组中） 。

例子…

数组：[2, 3, 10, 2, 4, 8, 1]

解：10 - 2 = 8

输出：8

---

数组：[7, 9, 5, 6, 3, 2]

解：9 - 7 = 2

输出：2

---

这是我所拥有的，但它不适用于所有测试……

 var a = [22, 2, 4, 5, 6, 444, 1, 666];

// declare variables
var minNumber = a[0],                   // initilize to first element
    maxNumber = a[0],                   // --- ^
    minNumberIndex = 0,                 // min index
    maxNumberIndex = a.length - 1;      // max index

// loop through each element in array
for(i = 0; i < a.length; i++) {

    // find min
    if (a[i] < minNumber && i < maxNumberIndex) {
        minNumber = a[i];
        minNumberIndex = i;
    }

    // find max
    if (a[i] >= maxNumber && i > minNumberIndex) {
        maxNumber = a[i];
        maxNumberIndex = i;
    }
}

// return results
console.log("max: \t" + maxNumber);
console.log("min: \t" + minNumber + "index: " + minNumberIndex);
console.log(maxNumber - minNumber);

请帮忙！

原文由 Kyle 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

O(n) 解决方案：

 function maxDifference(arr) {
  let maxDiff = -1;
  let min = arr[0];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > min && maxDiff < arr[i] - min) {
      maxDiff = arr[i] - min;
    }

    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return maxDiff;
}

console.log(maxDifference([1, 2, 3])); //2
console.log(maxDifference(3, 2, 1)); //-1
console.log(maxDifference([2, 3, 10, 2, 4, 8, 1])); //8
console.log(maxDifference([7, 9, 5, 6, 3, 2])); //2
console.log(maxDifference([22, 2, 4, 5, 6, 444, 1, 666])); //665
console.log(maxDifference([7, 9, 5, 6, 3, 2])); //2
console.log(maxDifference([666, 555, 444, 33, 22, 23])); //1
console.log(maxDifference([2, 3, 10, 2, 4, 8, 1])); //8

原文由 Volodymyr Myshko 发布，翻译遵循 CC BY-SA 4.0 许可协议