C++ এ সর্বোচ্চ ব্যবধান

ধরুন আমরা একটি অ্যারে আছে, যে সাজানো হয় না. আমরা তার সাজানো আকারে ধারাবাহিক উপাদানগুলির মধ্যে সর্বাধিক পার্থক্য খুঁজে বের করতে হবে। অ্যারেতে 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