查找数组中最大和最小数字的索引

Question

我需要创建一个函数，该函数查找它们之间差异最大的两个数字，并返回它们的索引作为两个元素的数组-[ lowest, biggest ]。

注意:较大的数字必须在最小数字的右边。如果两个数字之间没有差异，则函数必须返回[]。

function getProfit(arr) {
let result = [];
let sortedArr = arr.sort();
let min = sortedArr.indexOf(Math.min(...sortedArr));
let max = sortedArr.indexOf(Math.max(...sortedArr));
if(max > min) {
result.push(min);
result.push(max);
return result;
} else {
return [];
}
}
console.log(getProfit([13, 6, 3, 4, 10, 2, 3], [2, 4]));

Answer 1

你需要用两个指针(索引)遍历列表left和right，如下所述:您将以O(n)的时间复杂度完成您的解决方案。

function getProfit(arr) {
let result = [0,0];
for(let l=0,r=0; l<arr.length-1 && r<arr.length-1;r++){
if(arr[l] > arr[r]){
l++;
}else if(arr[r]-arr[l]> arr[result[1]]-arr[result[0]]){
result[0] = l;
result[1] = r;
}
}
return (result[1] === 0) ? [] : result;
}
console.log(getProfit([13, 6, 3, 4, 10, 2, 3]));