मान लीजिए हमारे पास एक वृत्ताकार सरणी (circular array) है (सरणी का अंतिम तत्व का अगला तत्व सरणी का पहला तत्व है), हमें हर तत्व के लिए अगली बड़ी संख्या (Next Greater Number) प्रदर्शित करनी है। यहां एक संख्या x की अगली बड़ी संख्या सरणी में उसकी अनुक्रमण क्रम में अगली पहली बड़ी संख्या है, इसका मतलब है हम उसकी अगली बड़ी संख्या खोजने के लिए वृत्ताकार खोज कर सकते हैं। यदि यह मौजूद नहीं है, तो यह -1 होगा। इसलिए यदि संख्याएँ [1, 2, 1, 3, 2, 1] हैं, तो आउटपुट होगा: [2,3,3,-1,3,2]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n := सरणी का आकार
- res नामक एक सरणी परिभाषित करें, आकार n का, और इसे -1 से भरें, st नामक एक स्टैक परिभाषित करें
- i को 0 से 2n तक की रेंज में
- index := i mod n, x := nums[index]
- जब तक st खाली नहीं है और nums[स्टैक के शीर्ष] < x
- res[स्टैक के शीर्ष] := x
- स्टैक से शीर्ष तत्व हटाएं
- index को स्टैक में सम्मिलित करें
- res लौटाएं
उदाहरण (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]
