查找数组中的最大差异

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);  

请帮忙！

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

Answer 2

let MaxDifference = arr => {
  let maxDiff = null;
  for(let x = 0; x < arr.length; x++){
    for(let y = x+1; y < arr.length; y++){
        if(arr[x] < arr[y] && maxDiff < (arr[y] - arr[x])){
            maxDiff = arr[y] - arr[x]
        }
    }
  }
  return maxDiff === null ? -1 : maxDiff;
}

Answer 3

您可以有两个数组。让我们称呼他们为minlr和maxrl。

minlr-在原始数组中从左到右minlr[i]存储索引之前的最小值的位置。i

maxrl-在原始数组中从右向左移动时，maxrl[i]存储直到索引为止的最大值。i

获得这两个数组后，您可以迭代数组并找到maxrl[i]和之间的最大差异minlr[i]。

在你上面的例子中：

1. minlr = {2,2,2,2,2,2,1};

   maxrl = {10,10,10,8,8,8,1};

   所以本例的答案是 10 - 2 = 8。

2. minlr = {7,7,5,5,3,2};

   maxrl = {9,9,6,6,3,2};

   所以本例的答案是 9 - 7 = 2