C ++中的最大差距
假设我们有一个未排序的数组。我们必须找到其排序形式的连续元素之间的最大差异。如果数组包含少于2个元素，我们将返回0。因此，如果数组类似于[12,3,9,1,17]，则输出将为6，因为排序后的数组将为[1,3,9,12,17]，所以5将是最大差3与9之差为6。
为了解决这个问题，我们将遵循以下步骤-
minVal：=inf，maxCal：=-inf
n：=nums的大小
如果n<2，则返回0；否则，返回0。
对于i，范围为0到n–1−
minVal：=nums[i]和minVal的最小值
maxVal：=nums[i]和maxVal的最大值
间隔：=maxVal–minVal/n–1的消除
制作一个大小为n–1的名为bucketMax的数组，并用–inf填充
制作一个大小为n–1的名为bucketMin的数组，并用inf填充
对于i，范围为0到n–1−
x：=nums[i]
如果x=minVal或x=maxVal，则跳过下一部分，进行下一次迭代
idx：=（nums[i]–minVal）/间隔。
bucketMax[idx]：=bucketMax[idx]和nums[i]的最大值
bucketMin[idx]：=bucketMin[idx]和nums[i]的最小值
ret：=0
上一页：=minVal
对于i，范围为0至n–1
如果bucketMax[i]=-inf和bucketMin[i]=inf，则跳过下一部分，进行下一次迭代
ret：=ret和bucketMin[i]的最大值–上一页
上一个：=bucketMax[i]
返回ret的最大值，maxVal-上一页
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maximumGap(vector<int>& nums) {
lli minVal = INT_MAX;
lli maxVal = INT_MIN;
int n = nums.size();
if(n < 2) return 0;
for(int i = 0; i < n; i++){
minVal = min((lli)nums[i], minVal);
maxVal = max((lli)nums[i], maxVal);
}
int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
vector <int> bucketMax(n - 1, INT_MIN);
vector <int> bucketMin(n - 1, INT_MAX);
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == minVal || x == maxVal) continue;
int idx = (nums[i] - minVal) / gap;
bucketMax[idx] = max(bucketMax[idx], nums[i]);
bucketMin[idx] = min(bucketMin[idx], nums[i]);
}
lli ret = 0;
lli prev = minVal;
for(int i = 0; i < n - 1; i++){
if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
ret = max(ret, bucketMin[i] - prev);
prev = bucketMax[i];
}
return max(ret, maxVal - prev);
}
};
main(){
Solution ob;
vector<int> v = {12,3,9,1,17};
cout << (ob.maximumGap(v));
}输入值
[12,3,9,1,17]
输出结果
6