最大間隙問(wèn)題 給定 n 個(gè)實(shí)數(shù)，求這n個(gè)實(shí)數(shù)在數(shù)軸上相鄰2個(gè)數(shù)之間的最大差值，設(shè)計(jì)解最大間隙問(wèn)題的線性時(shí)間算法
分析：
最直接的方法是接收n個(gè)輸入的實(shí)數(shù)后，排序（從小到大或者從大到小都可以），再計(jì)算它們之間的間隙，找出最大的間隙。但是因?yàn)橛信判颍筒粷M足線性時(shí)間算法。
可以用鴿籠原理（也叫做抽屜原理）解決
步驟：
1、接收輸入的實(shí)數(shù)，找出最大值和最小值

2、max和min可以通過(guò)遍歷得知，把min到max之間的間隙等分，分成n-1個(gè)區(qū)間，每個(gè)區(qū)間都是大小相等的。那么,min屬于第一個(gè)區(qū)間,max屬于最后一個(gè)區(qū)間。并且第i個(gè)區(qū)間的上限是第i+1個(gè)區(qū)間的下限。每個(gè)區(qū)間的大小為gap=(max-min)/(n-1)

3、把除去max和min的另外n-2個(gè)數(shù)放到n-1個(gè)區(qū)間里。numOfBucket是每個(gè)實(shí)數(shù)所屬的區(qū)間號(hào)，count數(shù)組中對(duì)應(yīng)的那個(gè)值加1，證明該區(qū)間擁有至少一個(gè)實(shí)數(shù)。把low[i]設(shè)置成max,把high[i]設(shè)置成min,是為了便于后面的判斷

4、最后判斷最大的間隙時(shí)，如果一個(gè)區(qū)間內(nèi)有兩個(gè)或者以上的實(shí)數(shù)，那么它們之間的間隙肯定不是最大的，因?yàn)檫@些數(shù)都擠到一塊了。相反，跨區(qū)間的數(shù)才可能產(chǎn)生最大的間隙

#include<stdio.h>  
int main(){  
    int n,i;  
    scanf("%d",&n);//輸入實(shí)數(shù)的個(gè)數(shù)  
    float*number=new float[n];     
    //接收n個(gè)實(shí)數(shù)   
    for(i=0;i<n;i++){  
        scanf("%f",&number[i]);  
    }  
      
    //找出其中的最大值和最小值  
    float max,min;  
    int maxIndex,minIndex;  
    max=min=number[0];  
    maxIndex=minIndex=0;  
    for(i=0;i<n;i++){  
        if(max<number[i]){  
            max=number[i];  
            maxIndex=i;  
        }  
        if(min>number[i]){  
            min=number[i];  
            minIndex=i;  
        }  
    }   
      
    //把除去max和min的另外n-2個(gè)數(shù)放到n-1個(gè)區(qū)間里  
    int*count=new int[n-1];    
    float*high=new float[n-1];    
    float*low=new float[n-1];    
    float gap=(max-min)/(n-1);  
    for(i=0;i<n-1;i++)    
    {    
        count[i]=0;    
        high[i]=min;    
        low[i]=max;    
    }    
    for(i=0;i<n-1;i++){  
        int numOfBucket=(int)((number[i]-min)/gap);  
        count[numOfBucket]++;  
        if(number[i]<low[numOfBucket]){  
            low[numOfBucket]=number[i];  
        }  
        if(number[i]>high[numOfBucket]){  
            high[numOfBucket]=number[i];  
        }  
    }  
      
    //第一個(gè)區(qū)間里面肯定有數(shù)，最起碼min在里面   
   
    float temp=0;    
    float left=high[0]; //第一個(gè)桶里肯定有數(shù)    
    //輸出最大的間距    
    for(i=1;i<n-1;i++)    
    {    
        if(count[i])    
        {     
            if(low[i]-left>temp)    
                temp=low[i]-left;    
            left=high[i];    
        }    
    }   
    printf("%.2f\n",temp);  
    return 0;  
}