leetcode Maximum Gap

class Solution { // 木桶排序 //鸽巢原理 public: int maximumGap(vector<int>& nums) { if (nums.size() < 2) return 0; int _min = *min_element(nums.begin(), nums.end()); int _max = *max_element(nums.begin(), nums.end()); double interval = (_max - _min) / (double)nums.size(); vector<pair<int, int>> vec(nums.size(), make_pair(0x7fffffff, 1)); for (int i = 0; i < nums.size(); ++i){ int k = (nums[i] - _min) / interval; vec[k].first = min (vec[k].first, nums[i]); vec[k].second = max (vec[k].second, nums[i]); } int ret = 0, last_max = 0; for (int i = 0; i < vec.size(); ++i){ if (vec[i].first <= vec[i].second){ if (last_max > 0) ret = max (ret, vec[i].first - last_max); ret = max (ret , vec[i].second - vec[i].first); last_max = vec[i].second; } } return ret; } };