**Leetcode 164. Maximum Gap | 桶排序

本文主要是介绍**Leetcode 164. Maximum Gap | 桶排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/maximum-gap/description/

思路：

(max-min)/(nums.size()-1) 这个是ans的下限，所以就把各个数字放进桶里，桶的大小就是这个下限。在一个桶里的数字的gap绝对不可能是ans（因为小于下限），只有相邻桶才可能是答案

class Solution {
public:int maximumGap(vector<int>& nums) {if (nums.size() <= 1) return 0;int mmin = nums[0], mmax = nums[0];for (int i = 1; i < nums.size(); i++) {mmin = min( mmin, nums[i] );mmax = max( mmax, nums[i] );}int bucket_size = (mmax - mmin)/(nums.size() - 1);if (bucket_size == 0) {if (mmax == mmin) return 0;bucket_size = 1;}int bucket_cnt = (mmax-mmin) / bucket_size;vector<int> bucket_min( bucket_cnt + 1, INT_MAX );vector<int> bucket_max( bucket_cnt + 1, INT_MIN );vector<int> b_cnt( bucket_cnt + 1, 0 );for (int i = 0; i < nums.size(); i++) {int bucket_id = (nums[i] - mmin) / bucket_size;b_cnt[bucket_id] ++;bucket_min[bucket_id] = min(bucket_min[bucket_id], nums[i]);bucket_max[bucket_id] = max(bucket_max[bucket_id], nums[i]);}int ans = INT_MIN, last_max = bucket_max[0];for (int i = 1; i < bucket_min.size(); i++) {if (!b_cnt[i]) continue;ans = max(bucket_min[i] - last_max, ans);last_max = bucket_max[i];}return ans;}
};

这篇关于**Leetcode 164. Maximum Gap | 桶排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---