C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-08-27

class MaxDivision {
public:
    int findMaxDivision(vector<int> A, int n) {
        sort(A.begin(),A.end());
        int maxsub=0;
        for(int i=1;i<n;i++){
            maxsub=max(maxsub,A[i]-A[i-1]);
        }
        return maxsub;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-05-25

class MaxDivision {
public:
    int findMaxDivision(vector<int> A, int n) {
        // write code here
        //计数排序--虽然我感觉不适合，因为当数组的（最大值-最小值）很大时，就不是O(n)了。
        int Max = INT_MIN, Min = INT_MAX;
        for(int i = 0; i < n; ++i){
            if(A[i] > Max) Max = A[i];
            if(A[i] < Min) Min = A[i];
        }
        vector<int> record(Max-Min+1, 0);
        for(int i = 0; i < n; ++i)
            record[A[i]-Min] = 1;
        int i = 0, j = 1, MAX_DIFF = INT_MIN;
        while(j <= Max-Min){
            if(record[j] && record[i]){
                if(j - i > MAX_DIFF) MAX_DIFF = j - i;
                ++i; ++j;
            }
            else{
                if(record[j]==0) ++j;
                if(record[i]==0) ++i;
            }
        }
        return MAX_DIFF;
    }
};