有一個整形數(shù)組A，請設計一個復雜度為O(n)的算法而姐，算出排序后相鄰兩數(shù)的最大差值腊凶。
給定一個int數(shù)組A和A的大小n，請返回最大的差值。保證數(shù)組元素多于1個吭狡。
測試樣例：
輸入：[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]);
}
}
// 遍歷每個桶內(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;
}
};
