最大差值

题目链接
时间复杂度
利用n个数放在n+1个桶中，必然有一个空桶，这也就否定了最大差值在桶内部。
然后记录每个桶中的最大值和最小值，最大差值在两个临近桶之间。
推荐看左神视频初级班第三讲100分钟左右
考查内容

桶排序

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3fffffff;
typedef long long LL;
LL m,n;
vector<LL> arr; 

LL bucket(LL x,LL Max, LL Min){
    return (x - Min)*n/(Max - Min); 
}
int main(){
    while(cin>>m){
        LL Max = -INF, Min = INF;
        LL x;
        char c;
        while(cin>>x){
            arr.push_back(x);
            if(x > Max) Max = x;
            if(x < Min) Min = x;
            c = getchar();
            if(c =='\n') break;
        }
        n = arr.size();
        if(Max == Min || n < 2){
            cout<<0<<endl;
            continue;
        }
        //n+1个桶中放n个数 
        vector<bool> hasNum(n+1); //标记桶的状态 
        vector<LL> maxs(n+1),mins(n+1); //记录桶中的最大值和最小值
        LL bid;
        for(LL i = 0; i < n; i++){
            bid = bucket(arr[i], Max, Min);
            maxs[bid] = hasNum[bid]? max(maxs[bid], arr[i]) : arr[i]; //保存最大值
            mins[bid] = hasNum[bid]? min(mins[bid], arr[i]) : arr[i];//保存最小值 
            hasNum[bid] = true;
        } 
        LL res = 0;
        LL lastMax = maxs[0];  

        for(LL i = 1; i <= n; i++){ //n+1个桶 
            if(hasNum[i]){
                res = max(res, mins[i] - lastMax); //全部桶里面找 
                lastMax = maxs[i];
            }
        }
        cout<<res<<endl;
    } 
    return 0;
}