ধরুন আমরা একটি অ্যারে আছে, যে সাজানো হয় না. আমরা তার সাজানো আকারে ধারাবাহিক উপাদানগুলির মধ্যে সর্বাধিক পার্থক্য খুঁজে বের করতে হবে। অ্যারেতে 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 −
রেঞ্জের i জন্য-
minVal :=mins of nums[i] এবং minVal
-
maxVal :=সংখ্যার সর্বাধিক [i] এবং maxVal
-
-
গ্যাপ :=maxVal – minVal / n – 1
এর সিলিং -
n – 1 আকারের bucketMax নামে একটি অ্যারে তৈরি করুন এবং এটি -inf দিয়ে পূরণ করুন
-
n – 1 আকারের bucketMin নামে একটি অ্যারে তৈরি করুন এবং এটি inf দিয়ে পূরণ করুন
-
0 থেকে n – 1 −
রেঞ্জের i জন্য-
x :=সংখ্যা[i]
-
যদি x =minVal বা x =maxVal হয়, তাহলে পরবর্তী অংশটি এড়িয়ে যান, পরবর্তী পুনরাবৃত্তির জন্য যান
-
idx :=(সংখ্যা[i] – minVal) / ফাঁক।
-
bucketMax[idx] :=সর্বোচ্চ bucketMax[idx] এবং সংখ্যা[i]
-
bucketMin[idx] :=bucketMin[idx] এবং সংখ্যা[i]
-
-
ret :=0
-
পূর্ববর্তী :=minVal
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি 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