题目

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。测试样例：[1,2,5,4,6],5返回：2

解析：

// 第20节 相邻两数最大差值练习题 // 基于桶排序的思想完成，不考虑两个相同的桶内的差值，只考虑该桶的最小值减去上一个桶的最大值，最大的就是最大值。class Gap {public:    int maxGap(vector
    
      A, int n) {        // write code here        // 第一次遍历：找到最值        int max_num = A[0];        int min_num = A[0];        for (int i = 1; i < A.size(); i++)        {            max_num = max(A[i], max_num);            min_num = min(A[i], min_num);        }        int len = max_num - min_num;        vector
     
       maxBucket(n, INT_MIN); //其实只有len个桶，将其映射到n        vector
      
        minBucket(n, INT_MAX);        // 第二次遍历        for (int i = 0; i < n; i++){            int index = (double)(A[i] - min_num) / len*(n - 1);            maxBucket[index] = max(A[i], maxBucket[index]);            minBucket[index] = min(A[i], minBucket[index]);        }        // 第三次遍历        int  res, pre = maxBucket[0];        for (int i = 1; i < n; i++){            if (minBucket[i] != INT_MAX){                res = max(res, minBucket[i] - pre);                pre = maxBucket[i];            }        }        return res;    }    int maxGap_1(vector
       
         A, int n) {        int minValue = A[0], maxValue = A[0];        for (int i = 1; i
        
         maxValue)                maxValue = A[i];            if (A[i] < minValue)                minValue = A[i];        }        vector
         
           bocketMax(n, INT_MIN); vector
          
            bocketMin(n, INT_MAX); int len = maxValue - minValue; if (len < 1) return 0; for (int i = 0; i < n; i++){ int index = (double)(A[i] - minValue) / len*(n - 1); bocketMax[index] = max(A[i], bocketMax[index]); bocketMin[index] = min(A[i], bocketMin[index]); } int res = 0, pre = bocketMax[0]; for (int i = 1; i < n; i++){ if (bocketMin[i] != INT_MAX){ res = max(res, bocketMin[i] - pre); pre = bocketMax[i]; } } return res; }};