ধারণা
একটি প্রদত্ত পূর্ণসংখ্যার বিন্যাসের ক্ষেত্রে, আমাদের কাজ হল অ্যারের প্রতিটি উপাদানের নিকটতম বাম এবং ডান ছোট উপাদানের মধ্যে সর্বাধিক নিখুঁত পার্থক্য নির্ধারণ করা৷ এটি লক্ষ করা উচিত যে যদি ডানদিকে বা বামে কোন ছোট উপাদান না থাকে যেকোন এলিমেন্টের সাইড তাহলে আমরা শূন্যকে ছোট এলিমেন্ট হিসেবে গ্রহণ করি। এখানে, সবচেয়ে বাম দিকের উপাদানের জন্য, বাম পাশের সবচেয়ে কাছের উপাদানটি 0 হিসেবে সেট করা হয়েছে। একইভাবে, সবচেয়ে ডানদিকের উপাদানের জন্য, ডান দিকের ক্ষুদ্রতম উপাদানটি 0 হিসেবে সেট করা হয়েছে।
ইনপুট
arr[] = {3, 2, 9} আউটপুট
2
বাম ছোট LS[] {0, 0, 2}
ডান ছোট RS[] {2, 0, 0}
abs-এর সর্বোচ্চ পার্থক্য(LS[i] - RS[i]) =2 - 0 =2
ইনপুট
arr[] = {3, 5, 9, 8, 8, 10, 4} আউটপুট
4
বাম ছোট LS[] ={0, 3, 5, 5, 5, 8, 3}
ডান ছোট RS[] ={0, 4, 8, 4, 4, 4, 0}
অ্যাবসের সর্বোচ্চ পার্থক্য(LS[i] - RS[i]) =8 - 4 =4
পদ্ধতি
আমরা একটি সহজ সমাধান প্রয়োগ করি যেখানে আমাদের কাজ হল প্রতিটি উপাদানের জন্য নিকটতম বাম এবং ডান ছোট উপাদানগুলি খুঁজে বের করা এবং তারপরে বাম এবং ডান ছোট উপাদানগুলির মধ্যে সর্বাধিক পার্থক্য আপডেট করা, এটি O(n^2) সময় ব্যয় করে।
আবার আমরা একটি কার্যকর সমাধান বাস্তবায়ন করি যা O(n) সময় ব্যয় করে। এখানে, আমরা একটি স্ট্যাক বাস্তবায়ন. এখানে, এখানে আকর্ষণীয় অংশ হল আমরা একই ফাংশন ব্যবহার করে বাম ছোট এবং ডান ছোট উভয় গণনা করি।
ধরুন ইনপুট অ্যারে হবে 'Array[]' এবং অ্যারের সাইজ হবে 'n'
বাম দিকের সমস্ত ছোট উপাদান নির্ধারণ করুন
- একটি নতুন খালি স্ট্যাক S এবং একটি অ্যারে LS তৈরি করুন[]
- এখন ইনপুট অ্যারে[]-এর প্রতিটি উপাদান 'Array[i]'-এর জন্য, যেখানে 'i' 0 থেকে n-1 পর্যন্ত যায়।
- যদিও S খালি থাকে না এবং S-এর উপরের উপাদান 'Array[i]':pop S এর থেকে বড় বা সমান হয়।
- যদি S খালি হয়:'Array[i]'-এর কোনো পূর্ববর্তী ছোট মান LS[i] =0 নেই
- অন্য:'অ্যারে[i]'-এর নিকটতম ছোট মান হল topof stackLS[i] =S.top()
- এস-এ 'অ্যারে[i]' চাপুন
- ডান দিকের সমস্ত ছোট উপাদান নির্ধারণ করুন
- প্রথমে বিপরীত অ্যারে অ্যারে[]। এখন অ্যারে বিপরীত করার পরে, ডান ছোট বাম ছোট হয়ে যায়।
- একটি অ্যারে RRS তৈরি করুন[] এবং RRS (LS-এর জায়গায়) পূরণ করতে ধাপ 1 এবং 2 পুনরাবৃত্তি করুন।
- আমরা -1 হিসাবে ফলাফল শুরু করি এবং প্রতিটি উপাদান অ্যারে[i] এর জন্য অনুসরণ করি। বিপরীত অ্যারের ক্ষেত্রে অ্যারে[i]-এর জন্য ডানদিকে ছোট RRS[n-i-1]রিটার্ন ফলাফল =max(ফলাফল, LS[i]-RRS[n-i-1]) এ সংরক্ষিত হয়
উদাহরণ
// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Shows function to fill left smaller element for every
// element of Array[0..n1-1]. These values are filled
// in SE1[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
// Build an empty stack
stack<int>S1;
// Visit all array elements
// Calculate nearest smaller elements of every element
for (int i=0; i<n1; i++){
// Used to keep removing top element from S1 while the top
// element is greater than or equal to Array[i]
while (!S1.empty() && S1.top() >= Array[i])
S1.pop();
// Used to store the smaller element of current element
if (!S1.empty())
SE1[i] = S1.top();
// It has been seen that if all elements in S were greater than Array[i]
else
SE1[i] = 0;
// Used to push this element
S1.push(Array[i]);
}
}
// Shows function returns maximum difference b/w Left &
// right smaller element
int findMaxDiff(int Array[], int n1){
int LS1[n1]; // To store left smaller elements
// find left smaller element of every element
leftSmaller(Array, n1, LS1);
// Determine right smaller element of every element
// first reverse the array and do the same process
int RRS1[n1]; // Used to store right smaller elements in
// reverse array
reverse(Array, Array + n1);
leftSmaller(Array, n1, RRS1);
// Determine maximum absolute difference b/w LS1 & RRS1
// In the reversed array right smaller for Array[i] is
// stored at RRS1[n1-i-1]
int result1 = -1;
for (int i=0 ; i< n1 ; i++)
result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
// return maximum difference between LS1 & RRS1
return result1;
}
// Driver program
int main(){
int Array[] = {3, 5, 9, 8, 8, 10, 4};
int n = sizeof(Array)/sizeof(Array[0]);
cout << "Maximum diff : "
<< findMaxDiff(Array, n) << endl;
return 0;
} আউটপুট
Maximum diff : 4
