[6kyu]Simple Fun #340: Minimum P

该算法题来自于 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;
}