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