该算法题来自于 codewars【语言: javascript】，翻译如有误差，敬请谅解~
- 介绍
- 在整数数组中，
gap表示两个相邻元素之间的差值。
-
Maximum gap是指所有间隙的最大值。 - 任务
- 给定一个排序后的整数数组
arr,从数组的内部任意移除一个元素（内部部分意味着不包括第一个和最后一个元素）。任务是返回在找到最小间隙进行删除操作后，出现的最大间隙。
- 例如：
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;
}
