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