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 लौटाएं;

• i को 0 से n - 1 तक की रेंज में -

  • minVal := nums[i] और minVal का न्यूनतम

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

• gap := 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) / gap.

  • bucketMax[idx] := bucketMax[idx] और nums[i] का अधिकतम

  • bucketMin[idx] := bucketMin[idx] और nums[i] का न्यूनतम

• ret := 0

• prev := minVal

• i को 0 से n - 1 तक की रेंज में

  • यदि bucketMax[i] = -inf और bucketMin[i] = inf, तो अगला भाग छोड़ें, अगले पुनरावृत्ति के लिए जाएं

  • ret := ret और bucketMin[i] - prev का अधिकतम

  • prev := bucketMax[i]

• ret, maxVal - prev का अधिकतम लौटाएं

उदाहरण

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

#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