最大间距问题

LeetCode164 最大间距 

 基数排序

#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int maximumGap(vector<int>& nums) {int n=nums.size();if(n<2) return 0;int exp=1;int Max=nums[0];vector<int> buf(n);for(int i=1;i<n;i++) Max=max(Max,nums[i]);while(exp<=Max){vector<int> cnt(10,0);for(int i=0;i<n;i++){int digit=(nums[i]/exp)%10;cnt[digit]++;}for(int i=1;i<10;i++) cnt[i]=cnt[i]+cnt[i-1];for(int i=n-1;i>=0;i--){int digit=(nums[i]/exp)%10;buf[cnt[digit]-1]=nums[i];cnt[digit]--;}copy(buf.begin(),buf.end(),nums.begin());exp*=10;}int res=0;for(int i=1;i<n;i++) res=max(nums[i]-nums[i-1],res);return res;}
};

分桶法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int maximumGap(vector<int>& nums){int Min=*min_element(nums.begin(),nums.end());int Max=*max_element(nums.begin(),nums.end());if(Max-Min<=1) return Max-Min;int n=nums.size();int d=(Max-Min+n-2)/(n-1);vector<pair<int,int>> buckets((Max-Min)/d+1,{0x3f3f3f3f,-0x3f3f3f3f});for(int i=0;i<n;i++){auto& [mn,mx]=buckets[(nums[i]-Min)/d];mn=min(nums[i],mn);mx=max(mx,nums[i]);}int res=0;int pre_max=0x3f3f3f3f;for(auto [mn,mx]:buckets){if(mx!=-0x3f3f3f3f){res=max(res,mn-pre_max);pre_max=mx;}}return res;}    
};