<center>最大間隙問(wèn)題

1.問(wèn)題描述

? ?給定n個(gè)實(shí)數(shù),求這n個(gè)數(shù)在實(shí)數(shù)軸上相鄰2個(gè)數(shù)之間的最大間隙，假設(shè)對(duì)任何實(shí)數(shù)的向下取整運(yùn)算耗時(shí)，設(shè)計(jì)一個(gè)線性時(shí)間算法解題。（數(shù)據(jù)的輸入由input.txt文件中讀得，算出的結(jié)果存到output.txt文件中。）

1.1 題目分析

• 問(wèn)題求相鄰的最大間距，輸入又是無(wú)序的，如若先進(jìn)行排序，則排序的復(fù)雜度最少是,不滿足線性時(shí)間復(fù)雜度要求。所以只能另想他法。
• 問(wèn)題聯(lián)想到組合數(shù)學(xué)中的插板問(wèn)題，將數(shù)字序列的上界和下界看成等差數(shù)列的首項(xiàng)和末項(xiàng)，每個(gè)公差的間距看成一個(gè)容器，根據(jù)等差數(shù)列的通項(xiàng)公式將每個(gè)數(shù)字放到容器中去。,所以數(shù)字散落在第個(gè)容器里。去除最小值，還剩下個(gè)數(shù)字，分布在n個(gè)容器里，遍歷容器至少有個(gè)空容器，有空的存在說(shuō)明有大間距存在。

1.2 想法可行性分析

??按照等差數(shù)列的通項(xiàng)公式 ，這樣就可以求出任意數(shù)據(jù)所在的位置。我們構(gòu)建n個(gè)相鄰容器，每個(gè)容器的寬度是公差d，第一個(gè)容器的起點(diǎn)是給定數(shù)字序列的最小值，第n個(gè)容器的起點(diǎn)是這個(gè)數(shù)字序列的最大值。

容器1	容器2		容器n

??當(dāng)把除去最小值之外的所有數(shù)字按照等差公式放入到相應(yīng)容器中時(shí)，由于有個(gè)數(shù)字，而容器卻有個(gè)，必然存在至少有一個(gè)容器為空。那么問(wèn)題就轉(zhuǎn)換為在遍歷個(gè)容器找尋其中最長(zhǎng)連續(xù)為空的容器。

2. 解題過(guò)程描述

2.1. 數(shù)據(jù)結(jié)構(gòu)

??要實(shí)現(xiàn)上面的想法，需要借助于數(shù)據(jù)結(jié)構(gòu)。需要構(gòu)建容器類，其中包括的成員變量包括：容器中數(shù)字的數(shù)量，容器中數(shù)字的最大值、最小值。類中的方法最主要的就是放置數(shù)字到容器中，該方法需要完成的工作包括：數(shù)字的數(shù)量+1；驗(yàn)證新放置的數(shù)字是否超過(guò)目前容器中數(shù)字的最值界限，若有，則更新最值。

#include <iostream>
#include <vector>
#include <math.h>
//抽屜類中包括元素個(gè)數(shù)，上界，下界，也可以有上下界索引
template<typename T>
class maxGap{
    private:
        int m_elemCount;
        T m_high;
        T m_low;

    public:
        maxGap():m_elemCount(0)
                 ,m_high(0.0)
                 ,m_low(0.0){}
        const T getHigh() const {return m_high;}
        const T getLow() const {return m_low;}
        const int getCount() const {return m_elemCount;}
        
        void insertElem(T elem){
            if(m_elemCount == 0){
                m_low = elem;
                m_high = elem;
            }
            else if(elem > m_high)
                m_high = elem;
            else if(elem < m_low)
                m_low = elem;
            m_elemCount ++ ;
        }
        
        
};

2.2. 算法描述及復(fù)雜度分析

??題干中要求時(shí)間的復(fù)雜度是線性的，下面我們來(lái)闡述算法流程和分析其時(shí)間復(fù)雜度。算法過(guò)程中主要的步驟包括：讀取文件，截取數(shù)字，放置數(shù)字到容器，遍歷容器找到最大間隙。

template<typename T>
T solveMaxGap(std::vector<T> arr){
    int len = arr.size();
    T max = getmax(arr);
    std::cout<<"max:"<<max<<std::endl;
    T min = getmin(arr);
    std::cout<<"min:"<<min<<std::endl;
    T dimen = (max - min)/(len - 1);
    std::cout<<"dimen:"<<dimen<<std::endl;
    T temp_high = arr[0] - arr[0];
    T maxgap = 0;
    T tempgap = 0;
    int zeroPos = 0;
    int zeroCount = 0;
    maxGap<T> temp;
    std::vector< maxGap<T> > container(100,temp);
    container[len - 1].insertElem(max);//最大值放在len-1的位置，非最值位于[0，len-2]
    //將元素放入桶中
    for(int i = 0 ;i < len; i++){
        if(arr[i] != max && arr[i] != min){
            int pos = floor((arr[i] - min )/ dimen);
    //      std::cout<<arr[i] <<"- "<< min<<"/"<<dimen <<":position:"<<pos<<std::endl;
            container[pos].insertElem(arr[i]);
        }
    }

    //遍歷桶，找到最長(zhǎng)的連續(xù)空桶，或最大間隙
    for(int i = 0;i < len ; i ++){
       if(container[i].getCount() == 0)
       {
           zeroPos = I;
           zeroCount ++;
       }
       else 
       {
           if(zeroCount == 0)
               continue;
           else{
               if(zeroPos - zeroCount < 0 ){
                   tempgap = container[zeroPos + 1].getLow() - min;
                   maxgap = (maxgap > tempgap)?maxgap:tempgap;               
               }

               else{
                   tempgap = container[zeroPos + 1].getLow() - container[zeroPos - zeroCount].getHigh();
                   //std::cout<<"tempgap : "<<tempgap<<std::endl;
                   maxgap = (maxgap > tempgap)?maxgap:tempgap;               
                   zeroCount = 0;
                   zeroPos = 0;
               }
           }

       }
    }
    return maxgap;

}

??程序中所有的循環(huán)都不存在嵌套，只存在遍歷線性容器，時(shí)間復(fù)雜度為，程序滿足題目要求。

2.3. 算法結(jié)果驗(yàn)證

result.png