मान लें कि हमारे पास एक गोलाकार सरणी है (अंतिम तत्व का अगला तत्व सरणी का पहला तत्व है), हमें प्रत्येक तत्व के लिए अगला ग्रेटर नंबर प्रदर्शित करना होगा। यहां एक संख्या x की अगली बड़ी संख्या, सरणी में इसके ट्रैवर्सिंग-ऑर्डर की पहली बड़ी संख्या है, इसका मतलब है कि हम इसकी अगली बड़ी संख्या को खोजने के लिए गोलाकार खोज कर सकते हैं। यदि यह मौजूद नहीं है, तो यह -1 होगा। इसलिए यदि संख्याएँ [1, 2, 1, 3, 2, 1] हैं, तो आउटपुट होगा:[2,3,3,-1,3,2]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n :=सरणी का आकार
- एक सरणी को परिभाषित करें जिसे रेस कहा जाता है, आकार n का, और इसे -1 से भरें, एक स्टैक सेंट को परिभाषित करें
- मैं के लिए 0 से 2n की सीमा में
- सूचकांक:=i mod n, x:=nums[index]
- जबकि सेंट खाली नहीं है और अंक [स्टैक के शीर्ष]
- रेस [स्टैक के शीर्ष] :=x
- स्टैक से शीर्ष तत्व हटाएं
- ढेर में अनुक्रमणिका डालें
उदाहरण(C++)
एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
} इनपुट
[1,2,1,3,2,1]
आउटपुट
[2,3,3,-1,3,2]