C++ এ প্রদত্ত অ্যারেতে প্রতিটি উইন্ডো আকারের জন্য সর্বনিম্ন সর্বোচ্চ খুঁজুন

এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রদত্ত অ্যারেতে প্রতিটি উইন্ডোর আকারের জন্য সর্বনিম্নটি ​​খুঁজে বের করা৷

সমস্যা বর্ণনা − আমাদের 1 থেকে n পর্যন্ত পরিবর্তিত একটি উইন্ডো আকারের সর্বনিম্ন সর্বাধিক খুঁজে বের করতে হবে। এর জন্য আমরা প্রদত্ত উইন্ডো আকারের সাবঅ্যারেগুলি বিবেচনা করব, প্রতিটি সাবয়ারের সর্বনিম্ন উপাদানটি খুঁজে বের করব এবং তারপরে সর্বনিম্নগুলির সর্বাধিকটি খুঁজে বের করব৷

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

arr[] ={4, 1, 2, 4, 5, 1, 2, 4}

আউটপুট

5 4 2 1 1 1 1 1 

ব্যাখ্যা

উইন্ডোর সাইজ :1 => জানালা { (4), (1), (2), (4), (5), (1), (2), (4) } => সর্বনিম্ন ={4, 1, 2, 4, 5, 1, 2, 4} => সর্বনিম্ন =52 => উইন্ডোজ { (4, 1), (1, 2), (2, 4), (4, 5), ( 5, 1), (1, 2), (2, 4) } => সর্বনিম্ন ={1, 1, 2, 4, 1, 1, 2} => সর্বনিম্ন =43 => উইন্ডোজ { (4, 1, 2), (1, 2, 4), (2, 4, 5), (4, 5, 1), (5, 1, 2), (1, 2, 4) } => সর্বনিম্ন ={ 1, 1, 2, 1, 1, 1} => সর্বনিম্ন =24 => উইন্ডোজ { (4, 1, 2, 4), (1, 2, 4, 5), (2, 4, 5), 1), (4, 5, 1, 2), (5, 1, 2, 4) } => সর্বনিম্ন ={1, 1, 1, 1, 1} => সর্বনিম্ন =15 => উইন্ডোজ { ( 4, 1, 2, 4, 5), (1, 2, 4, 5, 1), (2, 4, 5, 1, 2), (4, 5, 1, 2, 4) } => সর্বনিম্ন ={1, 1, 1, 1} => সর্বনিম্ন =16 => উইন্ডোজ { (4, 1, 2, 4, 5, 1), (1, 2, 4, 5, 1, 2), ( 2, 4, 5, 1, 2, 4) } => সর্বনিম্ন ={1, 1, 1} => সর্বনিম্ন =17 => উইন্ডোজ { (4, 1, 2, 4, 5, 1, 2) , (1, 2, 4, 5, 1, 2, 4) } => সর্বনিম্ন ={1, 1} => সর্বনিম্ন =17 => উইন্ডোজ { (4, 1, 2, 4, 5, 1, 2, 4) } => সর্বনিম্ন ={1} => সর্বনিম্ন সর্বোচ্চ =1

সমাধান পদ্ধতি

1 থেকে n আকারের সমস্ত উইন্ডো তৈরি করে সমস্যার একটি সহজ সমাধান। তারপর প্রদত্ত আকারের প্রতিটি উইন্ডোর জন্য, আমরা প্রদত্ত আকারের সমস্ত সাবয়ারে খুঁজে পাব। অ্যারের জন্য আমরা প্রতিটি সাবয়ারের সর্বনিম্ন খুঁজে পাব এবং তারপরে সর্বনিম্ন সর্বোচ্চটি ফেরত দেব।

প্রতিটি উইন্ডোর আকারের পুনরাবৃত্তির শেষে, আমরা স্কেলায় সর্বনিম্ন সবকটি সর্বোচ্চ প্রিন্ট করব

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;void printMaxMinWindowK(int arr[], int n, int k) { int maxMin =-1; int minEle =-1; জন্য (int i =0; i <=n-k; i++) { minEle =arr[i]; (int j =1; j  maxMin) maxMin =minEle; } cout< 
আউটপুট
 
উইন্ডোর সাইজ :1, সর্বনিম্ন :70 উইন্ডো সাইজ :2, সর্বনিম্ন :30 উইন্ডো সাইজ :3, সর্বনিম্ন :20 উইন্ডো সাইজ :4, সর্বনিম্ন :10 উইন্ডো সাইজ :5, সর্বনিম্ন :10 উইন্ডো সাইজ :6, সর্বনিম্ন সর্বোচ্চ :10
 
বিকল্প সমাধান
 

 সমস্যার একটি সহজ সমাধান হল অতিরিক্ত মেমরি স্পেস ব্যবহার করা, একটি অক্জিলিয়ারী অ্যারে তৈরি করা। বর্তমান উপাদানের জন্য পরবর্তী ক্ষুদ্রতম উপাদান সংরক্ষণ করতে আমরা একটি অ্যারে ব্যবহার করব। এবং আরেকটি পূর্ববর্তী ক্ষুদ্রতম উপাদান সংরক্ষণ করতে. এই অ্যারে ব্যবহার করে আমরা ইনডেক্স i এর অ্যারের উপাদানের উপাদান খুঁজে পাব। উপাদান arr[i] হল দৈর্ঘ্যের উইন্ডোর সর্বনিম্ন “right[i] - left[i] + 1”। এটি ব্যবহার করে, আমরা প্রদত্ত উইন্ডোটির জন্য সর্বনিম্ন সর্বোচ্চটি খুঁজে পাব।
 

 আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম, 
 
উদাহরণ
 
#include #include namespace ব্যবহার করে std;void printMaxMinWindow(int arr[], int n) { stacks; int prev[n+1]; int পরবর্তী [n+1]; জন্য (int i=0; i=arr[i]) s.pop(); যদি (!s.empty()) prev[i] =s.top(); s.push(i); } যখন (!s.empty()) s.pop(); জন্য (int i =n-1; i>=0; i-- ) { যখন (!s.empty() &&arr[s.top()]>=arr[i]) s.pop(); if(!s.empty()) next[i] =s.top(); s.push(i); } int maxOfMin[n+1]; জন্য (int i=0; i<=n; i++) maxOfMin[i] =0; জন্য (int i=0; i=1; i--) maxOfMin[i] =max(maxOfMin[i], maxOfMin[i+1]); (int i=1; i<=n; i++) cout<<"উইন্ডোর সাইজ:"< 
আউটপুট
 <প্রে>উইন্ডোর সাইজ:1, সর্বনিম্ন:5উইন্ডোর সাইজ:2, সর্বোচ্চ ন্যূনতম:4উইন্ডোর সাইজ:3, সর্বোচ্চ ন্যূনতম:2উইন্ডোর সাইজ:4, সর্বোচ্চ ন্যূনতম:1উইন্ডোর সাইজ:5, সর্বনিম্ন:1উইন্ডোর সাইজ :6, সর্বনিম্ন সর্বোচ্চ :1 উইন্ডোর আকার:7, সর্বনিম্ন সর্বোচ্চ :1 উইন্ডোর আকার:8, সর্বনিম্ন সর্বোচ্চ :1