ধরুন আমাদের একটি বৃত্তাকার অ্যারে আছে (শেষ উপাদানটির পরবর্তী উপাদানটি অ্যারের প্রথম উপাদান), আমাদের প্রতিটি উপাদানের জন্য পরবর্তী বৃহত্তর সংখ্যা প্রদর্শন করতে হবে। এখানে একটি সংখ্যা x এর পরবর্তী বৃহত্তর সংখ্যাটি অ্যারের পরবর্তী ট্র্যাভার্সিং-অর্ডারের প্রথম বৃহত্তর সংখ্যা, এর মানে আমরা এর পরবর্তী বৃহত্তর সংখ্যাটি খুঁজে পেতে বৃত্তাকারভাবে অনুসন্ধান করতে পারি। যদি এটি উপস্থিত না থাকে তবে এটি -1 হবে। সুতরাং যদি সংখ্যা [1, 2, 1, 3, 2, 1] হয়, তাহলে আউটপুট হবে:[2,3,3,-1,3,2]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=অ্যারের আকার
- রেস নামক একটি অ্যারে সংজ্ঞায়িত করুন, n আকারের, এবং এটিকে -1 দিয়ে পূরণ করুন, একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
- আমি 0 থেকে 2n
- পরিসরে
- index :=i mod n, x :=nums[index]
- যদিও st খালি নয় এবং nums[স্ট্যাকের উপরে]
- res[স্ট্যাকের উপরে] :=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]
