मान लीजिए कि हमारे पास एक सरणी है, जिसे क्रमबद्ध नहीं किया गया है। हमें क्रमबद्ध रूप में क्रमिक तत्वों के बीच अधिकतम अंतर ज्ञात करना है। यदि सरणी में 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
