问题描述：给定n个实数，求这些实数在实数见不鲜上相邻两个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，试设计最大间隙问题的线性时间算法。
解题思路：该问题其实并不复杂，最简单的思路是将给定的数进行排序，然后将排序后的数组扫描一下，得到两个数之间的最大间隙即可。问题复杂在要求的时间复杂度上，要求在O(1)时间内完成，这就要求对输入的数字扫描的次数不能超过N次，为此，可以采取鸽笼原理来进行。假设输入了N个数字，降去最大和最小两个元素外，还剩余N-2个元素，如果将这N-2个数字分配到N-1个区间里，则至少有一个空区间。而分配在区间内部两个元素的差一定小于区间的宽度，因此，最大间隙是一定存在的。而在处理区间时，需要记录三方面的东西：（1）区间内存储元素的数目；（2）区间的下限；（3）区间的上限。
public class Q1_5 {
public static void main(String[] args) {
int n;
float min, max;
float jiange;
int temp;
@SuppressWarnings("resource")
Scanner input = new Scanner(System.in);
System.out.println("输入数的个数：");
n = Integer.valueOf(input.nextLine());
System.out.println("输入每个数：");
float[] arr = new float[n];
float[] low = new float[n - 1];
float[] high = new float[n - 1];
float[] count = new float[n - 1];
for (int i = 0; i < n; i++) {
arr[i] = Float.valueOf(input.nextLine());
}
min = max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
jiange = (max - min) / (n - 1);
for (int i = 0; i < count.length; i++) {
low[i] = max;
high[i] = min;
}
for (int i = 0; i < arr.length; i++) {
temp = (int) ((arr[i] - min) / jiange);
if (temp == n - 1) {
temp -= 1;
}
if (low[temp] > arr[i]) {
low[temp] = arr[i];
}
if (high[temp] < arr[i]) {
high[temp] = arr[i];
}
count[temp]++;
}
float gap = 0, tempgap = 0, left = high[0];
for (int i = 1; i < n - 1; i++) {
if (count[i] > 0) {
tempgap = low[i] - left;
if (tempgap > gap) {
gap = tempgap;
}
left = high[i];
}
}
System.out.println(String.format("%.4f", gap));
}
}