該算法題來自于 codewars【語言: javascript】，翻譯如有誤差校读，敬請諒解~
- 介紹
- 在整數(shù)數(shù)組中俭厚，
gap表示兩個相鄰元素之間的差值。
-
Maximum gap是指所有間隙的最大值饮戳。 - 任務(wù)
- 給定一個排序后的整數(shù)數(shù)組
arr,從數(shù)組的內(nèi)部任意移除一個元素（內(nèi)部部分意味著不包括第一個和最后一個元素）。任務(wù)是返回在找到最小間隙進(jìn)行刪除操作后洞拨，出現(xiàn)的最大間隙扯罐。
- 例如：
arr = [1,2,5,7,8] // 返回 3
在這種情況下，我們可以刪除 2,5,7 的一個元素
刪除 2烦衣，[1,5,7,8] 的最大差值為 4 （1 到 5 之間的差值）
刪除 5歹河，[1,2,7,8] 的最大差值為 5 （2 和 7 之間的差值）
刪除 7掩浙，[1,2,5,8] 的最大差值為 3 （2 至 5，或 5 和 8 之間的差值）
刪除最小間隙后的最大差值是3
arr = [1,4,6] // 返回 5秸歧，移除 4 后厨姚，6-1=5
arr = [1,2,3,4,5] // 返回 2，移除 2,3,4 中任意元素键菱，最大差值都是 2
- 解答
- 其一
function minMaxGap(arr){
let arr2 = []; // 存儲最小差值
let arr3 = []; // 存儲最大差值
for(let i=0;i<arr.length-2;i++){
arr2.push(arr[i+2]-arr[i])
}
arr.forEach((el,i,arr)=>{
if(arr[i+2]-el == arr2.sort((a,b)=>a-b)[0]){
arr.splice(i+1,1);
for(let j=0;j<arr.length-1;j++){
arr3.push(arr[j+1]-arr[j])
}
}
});
return arr3.sort((a,b)=>b-a)[0];
}
- 其二
function minMaxGap(arr){
var max=0,min=Infinity
for(var i=0;i<arr.length-1;i++) if(arr[i+1]-arr[i]>max) max=arr[i+1]-arr[i]
for(var i=1;i<arr.length-1;i++) if(arr[i+1]-arr[i-1]<min) min=arr[i+1]-arr[i-1]
return Math.max(max,min)
}
- 其三
function minMaxGap(arr){
var maxGaps = [];
for(var i = 1; i < arr.length - 1; i++) {
var tmp = arr.slice(0,i).concat(arr.slice(i+1));
var gaps = new Array(tmp.length - 1).fill(0).map((v,i) => tmp[i + 1] - tmp[i]);
var max = Math.max(...gaps);
maxGaps.push(max);
}
return Math.min(...maxGaps);
}
- 其四
function minMaxGap(arr){
for (var m,min=Infinity,j=1;j<arr.length-1;min=m<min?m:min,j++)
for (var v,ar=arr.slice(0,j).concat(arr.slice(j+1)),m=0,i=0;++i<ar.length;) if ((v=ar[i]-ar[i-1])>m) m=v;
return min
}
- 其五
function minMaxGap(arr){
let min = 1/0, t, diff = a => Math.max(...a.slice(1).map((v,x)=>v-a[x]));
for(let i = 1; i < arr.length - 1; i++) {
t = diff(arr.filter((v,x)=>x!==i));
if(t < min) min = t;
}
return min;
}
