इस समस्या में, हमें 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(n2) कोटि की है।
एक बेहतर समाधान स्टैक और तत्वों के इंडेक्स का उपयोग करके समस्या को हल करना हो सकता है।
हम वर्तमान तत्व के अगले बड़े और छोटे तत्व के इंडेक्स को दो सरणियों nextGreater[] और nextSmaller[] में स्टोर करेंगे। इसका मतलब है कि सरणी nextGreater वर्तमान तत्व के अगले बड़े तत्व का इंडेक्स स्टोर करेगी। उदाहरण के लिए nextGreater[i] में अगले बड़े तत्व का इंडेक्स होगा जो arr[nextGreater[i]] होगा। और वही nextSmaller[] के लिए भी होगा।
तो, सरणी के अगले बड़े तत्व के अगले सबसे छोटे तत्व को एक्सेस करने के लिए। हम nextGreater[i] पर इंडेक्स के अगले छोटे तत्व को ढूंढेंगे। यह हमारे आवश्यक तत्व का इंडेक्स देगा, यानी आवश्यक तत्व arr[nextSmaller[nextGreater[i]]] है।
तत्व ढूंढने के लिए, हम स्टैक डेटा संरचना का उपयोग करेंगे जो शेष उपसरणी के तत्वों को स्टोर करेगा। यहां फ़ंक्शन बड़े तत्व ढूंढने के लिए कैसे काम करेगा।
=> हम सरणी को अंत से पार करेंगे, i -> n-1 से 0 तक।
=> यदि स्टैक खाली नहीं है और स्टैक का शीर्ष वर्तमान तत्व से छोटा है -> पॉप S, ऐसा तब तक करें जब तक बड़ा तत्व न मिल जाए या स्टैक खाली न हो जाए।
=> यदि स्टैक खाली है -> कोई बड़ा तत्व संभव नहीं, -1 स्टोर करें, nextGreater[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
