अवधारणा
एक दी गई पूर्णांकों की सरणी के संबंध में, हमारा कार्य सरणी में प्रत्येक तत्व के निकटतम बाएं और दाएं छोटे तत्व के बीच अधिकतम निरपेक्ष अंतर निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि यदि किसी तत्व के दाईं ओर या बाईं ओर कोई छोटा तत्व नहीं है तो हम शून्य को छोटे तत्व के रूप में स्वीकार करते हैं। यहां, उदाहरण के लिए बाएंmost तत्व के लिए, बाईं ओर निकटतम छोटा तत्व 0 के रूप में सेट किया जाता है। इसी तरह, दाएंmost तत्वों के लिए, दाईं ओर छोटा तत्व 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}
abs(LS[i] - RS[i]) का अधिकतम अंतर = 8 - 4 = 4
विधि
हम एक सरल समाधान लागू करते हैं जहां हमारा कार्य प्रत्येक तत्व के लिए निकटतम बाएं और दाएं छोटे तत्वों को ढूंढना है और उसके बाद बाएं और दाएं छोटे तत्व के बीच अधिकतम अंतर को अपडेट करना है, इसमें O(n^2) समय लगता है।
फिर हम एक कुशल समाधान लागू करते हैं जिसमें O(n) समय लगता है। यहां, हम एक स्टैक लागू करते हैं। यहां दिलचस्प हिस्सा यह है कि हम उसी फ़ंक्शन का उपयोग करके बाएं छोटे और दाएं छोटे दोनों की गणना करते हैं।
मान लें इनपुट सरणी 'Array[]' है और सरणी का आकार 'n' है
बाईं ओर सभी छोटे तत्व निर्धारित करें
- एक नया खाली स्टैक S और एक सरणी LS[] बनाएं
- अब इनपुट Array[] में प्रत्येक तत्व 'Array[i]' के लिए, जहां 'i' 0 से n-1 तक जाता है।
- जब तक S गैर-खाली है और S का शीर्ष तत्व 'Array[i]' से बड़ा या बराबर है: S को पॉप करें
- यदि S खाली है: 'Array[i]' का कोई पूर्ववर्ती छोटा मान नहीं है LS[i] = 0
- अन्यथा: 'Array[i]' का निकटतम छोटा मान स्टैक का शीर्ष है LS[i] = S.top()
- 'Array[i]' को S पर पुश करें
- दाईं ओर सभी छोटे तत्व निर्धारित करें
- सबसे पहले सरणी Array[] को उल्टा करें। अब सरणी को उल्टा करने के बाद, दाएं छोटे बाएं छोटे बन जाते हैं।
- एक सरणी RRS[] बनाएं और RRS को भरने के लिए चरण 1 और 2 को दोहराएं (LS के स्थान पर)।
- हम परिणाम को -1 के रूप में इनिशियलाइज़ करते हैं और प्रत्येक तत्व Array[i] के लिए निम्नलिखित करते हैं। उल्टी सरणी के संबंध में Array[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; // Array[0..n1-1] के प्रत्येक तत्व के लिए बाएं छोटे तत्व भरने वाला फ़ंक्शन। ये मान भरे जाते हैं // SE1[0..n1-1] में void leftSmaller(int Array[], int n1, int SE1[]){ // एक खाली स्टैक बनाएं stack<int>S1; // सभी सरणी तत्वों पर जाएं // प्रत्येक तत्व के निकटतम छोटे तत्वों की गणना करें for (int i=0; i<n1; i++){ // S1 से शीर्ष तत्व को तब तक हटाते रहें जब तक शीर्ष // तत्व Array[i] से बड़ा या बराबर है while (!S1.empty() && S1.top() >= Array[i]) S1.pop(); // वर्तमान तत्व के छोटे तत्व को संग्रहीत करने के लिए उपयोग किया जाता है if (!S1.empty()) SE1[i] = S1.top(); // यह देखा गया है कि यदि S में सभी तत्व Array[i] से बड़े थे else SE1[i] = 0; // इस तत्व को पुश करने के लिए उपयोग किया जाता है S1.push(Array[i]); } } // फ़ंक्शन बाएं और दाएं छोटे तत्व के बीच अधिकतम अंतर लौटाता है int findMaxDiff(int Array[], int n1){ int LS1[n1]; // बाएं छोटे तत्वों को संग्रहीत करने के लिए // प्रत्येक तत्व के बाएं छोटे तत्व खोजें leftSmaller(Array, n1, LS1); // प्रत्येक तत्व के दाएं छोटे तत्व निर्धारित करें // पहले सरणी को उल्टा करें और वही प्रक्रिया करें int RRS1[n1]; // उल्टी सरणी में दाएं छोटे तत्वों को संग्रहीत करने के लिए // उपयोग किया जाता है reverse(Array, Array + n1); leftSmaller(Array, n1, RRS1); // LS1 और RRS1 के बीच अधिकतम निरपेक्ष अंतर निर्धारित करें // उल्टी सरणी में Array[i] के लिए दाएं छोटे को // RRS1[n1-i-1] पर संग्रहीत किया जाता है int result1 = -1; for (int i=0 ; i< n1 ; i++) result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i])); // LS1 और RRS1 के बीच अधिकतम अंतर लौटाएं return result1; } // ड्राइवर प्रोग्राम 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
