问题描述：
最大间隔问题：给定 n 个实数 x1,x2,…,，求这 n 个数在实轴上相邻两个数之间的最大差值。假设对任何实数的下取整函数耗时 O(1)，设计解决最大间隔问题的线性时间算法。

算法设计：
对于给定的 n个实数 x1,x2,…,，计算它们的最大间隔。

数据输入：
输入数据由文件名为 input.txt 的文本文件提供。文件的第 1 行有 1 个正整数 n。
接下来的 1 行中有 n 个实数 x1,x2,…,。

结果输出：
将找到的最大间隔输出到文件 output.txt。

输入文件示例
input.txt

5
2.3 3.1 7.5 1.5 6.3

输出文件示例
output.txt

3.2

#include <iostream>
using namespace std;

/*
常规思路：先对数组排序，时间复杂度 𝑂(𝑛log⁡𝑛)再计算相邻元素的差值。
但我们要求 𝑂(𝑛)所以不能使用排序，而是利用抽屉原理，亦称鸽巢原理（the pigeonhole principle）的思想。
将 n+1 个物体，划分为 n 组，那么有至少一组有两个（或以上）的物体。
求解步骤：
1、找出数组中的最小值和最大值;
2、创建n−1个桶并初始化，每个桶的小值放数组最大值，大值放数组的最小值;
3、根据数组中n个元素的相对大小，将他们放在这n−1个桶中，可能有的桶中为空值，可能有的桶中含有多个元素，并记录每一个桶的最小值和最大值;（感觉和将数据放在数轴上对应的（n，n+1）区间内差不多）
4、用后一个桶的小值减去上一个桶的大值，得到桶之间的间隙，最后取出最大的那个间隙.
*/

#define MAXN 1000010

int n;//数据数量
double a[MAXN];//存储数据

double maxArray[MAXN];//一个桶中的最大值
double minArray[MAXN];//一个桶中的最小值

int count[MAXN];//桶中元素的个数

int main(){
    cin>>n;
    double maxVal=a[0],minVal=a[0];
    for(int i=0;i<n;i++){ 
        double temp=0; 
        cin>>temp;
        a[i]=temp;
        if(temp>maxVal){
            maxVal=temp;
        }
        if(temp<minVal){
            minVal=temp;
        }
    }
    fill(maxArray,maxArray+n,minVal);
    fill(minArray,minArray+n,maxVal);
    fill(count,count+n,0);
    double len=(maxVal-minVal)/(n-1);//桶的间隙,n个数据n-1个桶
    for(int i=0;i<n;i++){ 
        int index=(int)((a[i]-minVal)/len);//计算元素所在的桶,int()向下取整 
        if(a[i]>maxArray[index]) maxArray[index]=a[i];//更新最大值
        if(a[i]<minArray[index]) minArray[index]=a[i];//更新最小值
        count[index]++;
    }
    double ans=0;
    double tempMax=maxArray[0];//记录前一个桶的最大值
    for(int i=1;i<n-1;i++){ 
        if(count[i]!=0){ 
            double gap=minArray[i]-tempMax;//当前桶的最小值一定与前一个桶最大值相邻 
            if(gap>ans) ans=gap;
            tempMax=maxArray[i];//更新前一个桶的最大值
        }
    }
    printf("%.1lf",ans);
}