Khoảng cách tối đa trong C ++

Giả sử chúng ta có một mảng không được sắp xếp. Chúng ta phải tìm ra sự khác biệt lớn nhất giữa các phần tử liên tiếp ở dạng đã sắp xếp của nó. Chúng ta sẽ trả về 0 nếu mảng chứa ít hơn 2 phần tử. Vì vậy, nếu mảng giống như [12,3,9,1,17], thì đầu ra sẽ là 6, vì mảng được sắp xếp sẽ là [1,3,9,12,17] vì vậy 5 sẽ là sự khác biệt lớn nhất như chênh lệch giữa 3 và 9 là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

minVal:=inf, maxCal:=-inf
n:=kích thước của nums
nếu n <2, thì trả về 0;
cho tôi trong phạm vi từ 0 đến n - 1 -
- minVal:=min of nums [i] and minVal
- maxVal:=max of nums [i] và maxVal
gap:=celing of maxVal - minVal / n - 1
tạo một mảng có tên là bucketMax có kích thước n - 1 và điền vào mảng này bằng –inf
tạo một mảng có tên là bucketMin có kích thước n - 1 và điền vào mảng này với inf
cho tôi trong phạm vi từ 0 đến n - 1 -
- x:=nums [i]
- nếu x =minVal hoặc x =maxVal thì bỏ qua phần tiếp theo, chuyển sang lần lặp tiếp theo
- idx:=(nums [i] - minVal) / khoảng trống.
- bucketMax [idx]:=max của bucketMax [idx] và nums [i]
- bucketMin [idx]:=min of bucketMin [idx] and nums [i]
ret:=0
trước:=minVal
cho tôi trong phạm vi từ 0 đến n - 1
- nếu bucketMax [i] =-inf và bucketMin [i] =inf, thì bỏ qua phần tiếp theo, chuyển sang lần lặp tiếp theo
- ret:=max của ret và bucketMin [i] - trước
- trước:=bucketMax [i]
trả về tối đa ret, maxVal - trước

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[12,3,9,1,17]

Khoảng cách tối đa trong C ++

Ví dụ

Đầu vào

Đầu ra