अवधारणा
दिए गए पूर्णांकों की एक सरणी के संबंध में, हमारा कार्य सरणी में प्रत्येक तत्व के निकटतम बाएँ और दाएँ छोटे तत्व के बीच अधिकतम निरपेक्ष अंतर को निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि यदि दाईं ओर या बाईं ओर कोई छोटा तत्व नहीं है किसी भी तत्व के पक्ष में तो हम शून्य को छोटे तत्व के रूप में स्वीकार करते हैं। यहां, उदाहरण के लिए, बाईं ओर के सबसे छोटे तत्व को बाईं ओर के सबसे छोटे तत्व को 0 के रूप में सेट किया गया है। उसी तरह, सबसे दाहिने तत्वों के लिए, दाईं ओर के छोटे तत्व को 0 के रूप में सेट किया गया है।
इनपुट
arr[] = {3, 2, 9} आउटपुट
2
बायां छोटा LS[] {0, 0, 2}
दायां छोटा RS[] {2, 0, 0}
एब्स का अधिकतम अंतर(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) समय की खपत करता है। यहां, हम एक स्टैक लागू करते हैं। यहाँ, दिलचस्प बात यह है कि हम एक ही फ़ंक्शन का उपयोग करके बाएँ छोटे और दाएँ छोटे दोनों की गणना करते हैं।
मान लें कि इनपुट ऐरे 'ऐरे []' हो और ऐरे का आकार 'एन' हो
बाईं ओर सभी छोटे तत्व निर्धारित करें
- एक नया खाली स्टैक S और एक सरणी LS बनाएं[]
- अब इनपुट ऐरे में प्रत्येक तत्व 'ऐरे [i]' के लिए [], जहां 'i' 0 से n-1 तक जाता है।
- जबकि S गैर-रिक्त है और S का शीर्ष तत्व 'Array[i]':pop S से बड़ा या उसके बराबर है
- अगर S खाली है:'Array[i]' का कोई पूर्ववर्ती छोटा मान नहीं हैLS[i] =0
- else:'ऐरे [i]' का निकटतम छोटा मान स्टैक के ऊपर हैLS[i] =S.top()
- 'ऐरे[i]' को S पर पुश करें
- दाईं ओर सभी छोटे तत्वों को निर्धारित करें
- पहले रिवर्स ऐरे ऐरे में []। अब सरणी को उलटने के बाद, दायां छोटा बाएं छोटा हो जाता है।
- एक सरणी बनाएं RRS[] और RRS (LS के स्थान पर) भरने के लिए चरण 1 और 2 दोहराएँ।
- हम परिणाम को -1 के रूप में प्रारंभ करते हैं और प्रत्येक तत्व के लिए निम्नलिखित करते हैंअरे [i]। उलटे सरणी के संबंध में Array[i] के लिए सही छोटा RRS[n-i-1]return result =max(result, 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