因为时间复杂度为O(n)所以选择桶排序算法
class Solution { public: int maximumGap(vector<int>& nums) { //使用什么方法呢 int len = nums.size(); if (len<2) return 0; int maxval = INT_MIN; int minval = INT_MAX; for (int i = 0; i<len; ++i)//求最大值和最小值 { maxval = maxval>nums[i] ? maxval : nums[i]; minval = minval<nums[i] ? minval : nums[i]; } if (minval == maxval) return 0; //求桶的大小以及桶的数量是多少 int tong_size = max(1,(maxval - minval) / (len - 1)); int tong_num = (maxval - minval) / tong_size + 1; //int* tong=new int[tong_num]; int* tong_max = new int[tong_num]; int* tong_min = new int[tong_num]; //初始化桶的每个元素 for (int i = 0; i < tong_num; ++i) { tong_max[i] = INT_MIN; tong_min[i] = INT_MAX; } for (int i = 0; i<len; ++i)//依次向桶中对应的位置添加元素并且把每个桶的最大和最小元素存储起来 { int index = (nums[i] - minval) / tong_size; tong_max[index] = max(tong_max[index], nums[i]); tong_min[index] = min(tong_min[index], nums[i]); //cout << "aaa" << endl; } //现在开始遍历 int pre = minval; int maxGap = 0; for (int k = 0; k<tong_num; ++k) { if (tong_min[k] == INT_MAX&&tong_max[k] == INT_MIN) continue; maxGap = max(maxGap, tong_min[k] - pre); pre = tong_max[k]; } return maxGap; } };