算法题巧解之数组排序后相邻最大差值

最近在复习算法知识，然后今天在学习的过程中遇到了一个很经典的问题，所以做笔记记录一下 ~_~

题目：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)

例：

数组 arr =[1,3,2,5,8,6]
输出结果：2

看到这个题目我的第一反应是通过多次遍历的这样暴力手段来解决（请原谅我的菜和无知），但后来了解到这个题目可以用一种十分巧妙的方法来解决。

思路：
这个巧妙的方法和桶排序有很大的相似之处。首先，定义一个长度为待排序数组（下文中用arr代替）的长度+1的数组用来抽象的表示桶；将arr中的最小值和最大值分别放置在桶的头部和尾部，将arr中数的大小范围分成 arr.length+1个部分,也就是桶的个数，每个桶存连续长度的一个范围的数，但是为了减少不必要的操作，只存一个范围内的最大值和最小值，相邻最大差一定是某个桶的最大值和它相邻的下一个桶的最小值的差。

根据思路可以写出下面代码：

function getMaxAfterSort(arr){
    if(arr==null||arr.length<2){
        return 0;
    }
    var len = arr.length;
    var min = Number.MAX_VALUE;
    var max = Number.MIN_VALUE;
    // 获取最大值和最小值
    for(var i=0;i<len;i++){
        min = min > arr[i] ? arr[i] : min;
        max = max > arr[i] ? max : arr[i];
    }
    if(min == max)
        return 0;
    // 每个桶信息的描述，分别为存在标识，最小值，最大值
    var hasNum = new Array(len+1);
    var mins = new Array(len+1);
    var maxs = new Array(len+1);
    var sign;
    for(var i=0; i<len; i++){
        sign = judgeBucket(arr[i],len,min,max);
        hasNum[sign] = true;
        mins[sign] = hasNum[sign] ? Math.min(mins[sign],arr[i]):arr[i];
        maxs[sign] = hasNum[sign] ? Math.max(maxs[sign],arr[i]):arr[i];
    }

    var res = 0;
    lastMax = maxs[0];
    // 遍历返回最大差值
    for(var j=1;j<len+1;j++){
        if(hasNum[j]){
        res = Math.max(res,mins[j]-lastMax);
        lastMax = maxs[j];
        }
    }
    return res;
}

// 返回num存入的桶的下标
function judgeBucket(num,len,min,max){
    return Math.floor((num-min)*len/(max-min));
}