有一個(gè)整形數(shù)組A，請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(n)的算法，算出排序后相鄰兩數(shù)的最大差值。

給定一個(gè)int數(shù)組A和A的大小n，請(qǐng)返回最大的差值。保證數(shù)組元素多于1個(gè)。

測(cè)試樣例：
輸入：[1,2,5,4,6],5
返回：2

class Gap {
public:
    int maxGap(vector<int> A, int n) {
        // write code here
        int max = A[0], min = A[0];
        int max_idx = 0, min_idx = 0;
        for(int i=1; i<n; i++){
            if(A[i] > max){
                max = A[i];  max_idx = i;
            }else if (A[i] < min){
                min = A[i];  min_idx = i;
            }
        }
        float step = (max - min) / (float)n;
        vector< list<int> > bucket(n+1);
        bucket[0].push_back(A[min_idx]);
        bucket[n].push_back(A[max_idx]);
        
        // 遍歷數(shù)組，將元素放入桶內(nèi)
        for(int i=0; i<n; i++){
            if(i==min_idx || i==max_idx){
                continue;
            }else{
            bucket[floor((A[i] - min)/step)].push_back(A[i]);
            }
        }

        // 遍歷每個(gè)桶內(nèi)的list，找出該桶內(nèi)的最大值與與下一桶內(nèi)最小值
        int max_gap = 0;
        int l_max = 0;
        int r_min = 0, r_max = 0;
        for(int i=0; i<n+1; ++i){
            if(!bucket[i].empty()){
                r_max = bucket[i].front();
                r_min = bucket[i].front();
                list<int>::iterator j = bucket[i].begin(); 
                for(; j!=bucket[i].end(); ++j){
                    if(*j > r_max){
                        r_max = *j;
                    }else if(*j < r_min){
                        r_min = *j;
                    }
                }
                if(i>0){
                    max_gap = r_min - l_max > max_gap ? r_min - l_max : max_gap;
//                    if(r_min - l_max > max_gap){
//                        max_gap = r_min - l_max;
//                    }
                }
                l_max = r_max;
            }
        }
        return max_gap;
    }
};