转自：
阿里巴巴面试算法题目：有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间
题目：有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是 要求线性空间和线性时间用基于桶排序的方式。注意到，最后只需要求间隔的最大值，所以任何间隔小于bar= (max – min)/(N-1) 的值都可以不计。这样，首先求随机数组中的max , min 这些都是线性时间的然后，分配从[min, max]间分配(N-1)个桶，，每个桶是一个有序实数对，(a,b)将所有数往桶里塞，把欲塞进去的数记为x，
(空桶)如果桶里本身没有数，那么a=b=x(桶内已有数)如果x>b，那么b=x,如果x <a那么a=x，反正就是说这个桶里的(a,b)表示进入该桶中的数的范围。此操作是线性的。然后按顺序对每个相邻桶（跳过没有数的桶）进行比较。例如，相邻桶(a,b), (c,d)的距离D = 就是c – b最终就是，比较的D的最大值。这时间也是线性的。空间也是线性的。可能的问题：为什么我不必计算(b-a)或者(d-c)呢？很显然，b-a和d-c都是 <bar的，最大相邻间隔肯定是大于bar的。
#include <stdio.h>int MaxDiff(int a[], int n){int max, min, i;max = min = a[0];for (i=1; i < n; ++i){ if (a[i] > max)max = a[i]; if (a[i] < min)min = a[i];}int bar, pos;bar = (max-min)/(n-1);int (*bucket)[2] = new int[n][2](); //初始化数组 [0]放桶中最小 [1]放桶中最大值memset(bucket, 0, n*2*sizeof(int));for (i=0; i<n; ++i){ pos = (a[i]-min)/bar; if (bucket[pos][0] == 0) {bucket[pos][0] = bucket[pos][1] = a[i]; } else {if (a[i] > bucket[pos][1])bucket[pos][1] = a[i];if (a[i] < bucket[pos][0])bucket[pos][0] = a[i]; }}int max_diff, diff;max_diff = 0;for (i=1; i<n; ++i){ if (bucket[i][0] != 0) {diff = bucket[i][0] – bucket[i-1][1];if (max_diff < diff)max_diff = diff; }}delete[] bucket;return max_diff;}int main(){int b[] = {3, 89, 76, 23, 23, 87};printf("%d", MaxDiff(b, 4));return 0;}
积极的人在每一次忧患中都看到一个机会，
