1. 从一个已知数组中取出两个数a, b的index:a必须在b前;b-a的值是最大的;
const list = [0, 3, 5, 9, 7, 14, 2, 12, 5, 12];
// const list = [18, 3, 5, 9, 7, 14, 2, 12, 5, 12];
// const list = [1, 2, 3, 4, 5, 6, 7, 8];
// const list = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
解法1:首先取每个数a与其之后的数b计算取差值,以a的index为key存储差值最大的结果到一个字典里;遍历该字段比较所有差值,找出最大的结果。
var buffer = {};
for (var index = 0; index < list.length; index++) {
var o = list[index];
var dif = null, _index = index + 1;
for (var i = index + 1; i < list.length; i++) {
const b = list[i];
if (dif == null) {
dif = b - o;
} else if (dif <= b - o) {
dif = b - o;
_index = i;
}
}
buffer[index] = {leftIndex: index, rightIndex: _index, difference: dif};
}
const keys = Object.keys(buffer);
var result = buffer[keys[0]];
for(var i = 1; i < keys.length; i ++) {
const key = keys[i];
const item = buffer[key];
if (item.difference != null && result.difference < item.difference) {
result = item;
}
}
console.log(result)
解法2: 后数永远与前数中最小值作差,再将差值与前数差值中最大的值作比较,最好取最大差值对应前数与后数的index
var leftNum = list[0];
var rightNum = list[1];
var difference = rightNum - leftNum;
var minNum = leftNum > rightNum ? rightNum : leftNum;
var leftIndex = 0;
var rightIndex = 1;
var bufIndex = leftNum > rightNum ? rightIndex : leftIndex;
for (var i = 2; i < list.length; i++)
{
// 将当前元素和它之前的最小元素进行相减,当差值更大,更新记录的元素
if (list[i] - minNum > difference)
{
leftNum = minNum;
rightNum = list[i];
difference = list[i] - minNum;
leftIndex = bufIndex;
rightIndex = i;
}
if (list[i] < minNum) // 如果当前元素是最新的最小数,更新当前最小的数
{
bufIndex = i;
minNum = list[i];
}
}
console.log(
"leftIndex: " + leftIndex ,
"leftNum: " + leftNum,
"rightIndex: " + rightIndex,
"rightNum: " + rightNum,
"difference: " + difference);