এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার মান সমন্বিত একটি অ্যারে arr[] দেওয়া হয়েছে। আমাদের কাজ হল একটি অ্যারেতে পরবর্তী বৃহত্তরের পরবর্তী ছোটটিকে খুঁজে বের করা৷
৷সমস্যা বর্ণনা − আমরা অ্যারের বর্তমান উপাদানের চেয়ে বড় একটি উপাদান খুঁজে পাব এবং তারপরে আমরা অ্যারেতে এমন উপাদানটি খুঁজে পাব যা এই বৃহত্তর উপাদানটির চেয়ে ছোট। এবং যদি অ্যারেতে পরবর্তী কোন ছোট বা পরবর্তী বৃহত্তর উপাদান বিদ্যমান না থাকে তাহলে রিটার্ন -1।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 2, 8, 3, 9, 1} আউটপুট
{3, 3, 1, 1, -1, -1} ব্যাখ্যা
পরবর্তী বৃহত্তর উপাদানগুলির অ্যারে:{8, 8, 9, 9, -1, -1} যেহেতু 9 হল অ্যারের বৃহত্তম উপাদান এবং 1 হল শেষ উপাদান, তাদের পরবর্তী বৃহত্তর উপাদান নেই৷
পরবর্তী বৃহত্তর উপাদানগুলির পরবর্তী ছোটের অ্যারে :{3, 3, 1, 1, -1, -1}
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অ্যারের উপর এবং অ্যারের প্রতিটি উপাদানের জন্য পুনরাবৃত্তি করে,
-
অ্যারে থেকে পরবর্তী বৃহত্তর উপাদান খুঁজুন।
-
অবশিষ্ট অ্যারেতে এই বৃহত্তর উপাদানটির থেকে একটি ছোট উপাদান খুঁজুন।
এই সমাধানটি তার কাজটি করতে পারে তবে সময়ের জটিলতাটি O(n 2 ক্রম অনুসারে) )।
একটি ভাল সমাধান সমস্যাটির জন্য উপাদানগুলির স্ট্যাক এবং সূচী ব্যবহার করা যেতে পারে।
আমরা অ্যারেতে কারেন্ট এলিমেন্টের পরবর্তী বৃহত্তর এবং ছোট এলিমেন্টের ইনডেক্স nextGreater[] এবং nextSmaller[] নামে দুটি অ্যারেতে সংরক্ষণ করব। এর মানে অ্যারে nextGreater বর্তমান উপাদানের পরবর্তী বৃহত্তর উপাদানের সূচক সংরক্ষণ করবে। যেমন nextGreater[i]-এ পরবর্তী বৃহত্তর উপাদানের সূচক থাকবে যা হবে arr[nextGreater[i]]। এবং পরবর্তী ছোট[] এর জন্যও একই হবে।
সুতরাং, অ্যারের পরবর্তী বৃহত্তর উপাদানের পরবর্তী ক্ষুদ্রতম উপাদান অ্যাক্সেস করতে। আমরা নেক্সট গ্রেটার[i] এ সূচকের পরবর্তী ছোট উপাদানটি খুঁজে পাব। এটি আমাদের প্রয়োজনীয় উপাদানের সূচক দেবে, অর্থাৎ প্রয়োজনীয় উপাদানটি হল arr[nextSmaller[nextGreater[i]]]।
উপাদান খুঁজে বের করার জন্য, আমরা স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করব যা অবশিষ্ট সাবয়ারের উপাদানগুলিকে সংরক্ষণ করবে। বৃহত্তর উপাদান খোঁজার জন্য ফাংশনটি কীভাবে কাজ করবে তা এখানে।
-
=> আমরা শেষ থেকে অ্যারে অতিক্রম করব, i -> n-1 থেকে 0.
-
=> যদি স্ট্যাকটি খালি না হয় এবং স্ট্যাকের উপরের অংশ বর্তমান উপাদান -> পপ এস থেকে ছোট হয়, তাহলে এটি করুন যতক্ষণ না একটি বড় উপাদান পাওয়া যায় বা স্ট্যাকটি খালি না হয়।
-
=> স্ট্যাক খালি থাকলে -> এর চেয়ে বড় কোনো উপাদান সম্ভব নয়, স্টোর -1, নেক্সটগ্রেটার[i] =-1।
-
=> অন্য -> পরবর্তী বৃহত্তর উপাদানটি স্ট্যাকের শীর্ষে রয়েছে, স্ট্যাকের শীর্ষে সংরক্ষণ করুন, nextGreater[i] =stack.top()।
-
=> বর্তমান উপাদানটিকে স্ট্যাকের মধ্যে পুশ করুন, stack.push()
একই পদ্ধতি অ্যারের বর্তমান উপাদানের জন্য পরবর্তী ছোট উপাদান খুঁজে পেতে ব্যবহার করা যেতে পারে। এবং একবার আমরা উভয়ের সূচী খুঁজে পেয়েছি। অ্যারে থেকে প্রয়োজনীয় উপাদান খুঁজে পেতে আমরা এই সূচীগুলি ব্যবহার করতে পারি।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
stack<int> nextGreater;
int i = n-1;
while(i >= 0) {
while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i] )
nextGreater.pop();
if (!nextGreater.empty())
next[i] = nextGreater.top();
else
next[i] = -1;
nextGreater.push(i);
i--;
}
}
void findNextSmaller(int arr[], int n, int next[]) {
stack<int> nextSmaller;
int i = n-1 ;
while(i >= 0){
while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
nextSmaller.pop();
if (!nextSmaller.empty())
next[i] = nextSmaller.top();
else
next[i] = -1;
nextSmaller.push(i);
i -- ;
}
}
void findNextSmallerofNextGreaterElemenetArray(int arr[], int n) {
int nextGreaterIndex[n];
int nextSmallerIndex[n];
findNextGreater(arr, n, nextGreaterIndex);
findNextSmaller(arr, n, nextSmallerIndex);
for (int i=0; i< n; i++){
if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
cout<<arr[nextSmallerIndex[nextGreaterIndex[i]]]<<"\t";
else
cout<<"-1"<<"\t";
}
}
int main(){
int arr[] = {4, 2, 8, 3, 9, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"All next smaller of next greater elements of the array are ";
findNextSmallerofNextGreaterElemenetArray(arr, n);
return 0;
} আউটপুট
All next smaller of next greater elements of the array are 3 3 1 1 -1 -1
