सी++ में अधिकतम गैप

मान लीजिए कि हमारे पास एक सरणी है, जिसे क्रमबद्ध नहीं किया गया है। हमें क्रमबद्ध रूप में क्रमिक तत्वों के बीच अधिकतम अंतर ज्ञात करना है। यदि सरणी में 2 से कम तत्व हैं तो हम 0 लौटाएंगे। तो अगर सरणी [12,3,9,1,17] की तरह है, तो आउटपुट 6 होगा, क्योंकि क्रमबद्ध सरणी [1,3,9,12,17] होगी, इसलिए 5 अधिकतम अंतर होगा 3 और 9 के बीच का अंतर 6 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• minVal :=inf, maxCal :=-inf

• n :=अंकों का आकार

• अगर n <2, तो 0 लौटाएं;

• मैं के लिए 0 से n - 1 की सीमा में -

  • minVal :=min of nums[i] and minVal

  • maxVal :=अधिकतम अंक[i] और maxVal

• गैप:=मैक्सवेल की सीलिंग - मिनवैल / एन - 1

• बकेटमैक्स नामक एक सरणी बनाएं जिसका आकार n-1 है, और इसे -inf से भरें

• बकेटमिन नामक एक सरणी बनाएं जिसका आकार n-1 है, और इसे inf से भरें

• मैं के लिए 0 से n - 1 की सीमा में -

  • एक्स:=अंक [i]

  • अगर x =minVal या x =maxVal, तो अगला भाग छोड़ें, अगले पुनरावृत्ति के लिए जाएं

  • idx :=(अंक [i] - minVal) / गैप।

  • बकेटमैक्स[idx] :=अधिकतम बकेटमैक्स[idx] और अंक[i]

  • बकेटमिन [idx] :=बकेटमिन का न्यूनतम [idx] और अंक [i]

• रिट:=0

• पिछला :=minVal

• मेरे लिए 0 से n - 1 की सीमा में

  • अगर बकेटमैक्स [i] =-inf और बकेटमिन [i] =inf, तो अगला भाग छोड़ें, अगले पुनरावृत्ति के लिए जाएं

  • रिट :=अधिकतम रिट और बकेटमिन [i] - पिछला

  • पिछला :=बकेटमैक्स[i]

• रिट का अधिकतम रिटर्न, मैक्सवैल - पिछला

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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