এই সমস্যায় একটি সার্কুলার অ্যারে দেওয়া থাকলে, প্রতিটি এলিমেন্টের জন্য নেক্সট গ্রেটার এলিমেন্ট বের করতে হবে। সার্কুলার মানে শেষ এলিমেন্টের পর প্রথম এলিমেন্ট। না পেলে -1।
উদাহরণ: [1,2,1,3,2,1] -> আউটপুট [2,3,3,-1,3,2]।
সমাধানের পদ্ধতি (Monotonic Stack + Circular Traversal)
- রেজাল্ট অ্যারে
-1দিয়ে ইনিশিয়ালাইজ করুন। - স্ট্যাকে ইন্ডেক্স রাখুন (মনোটোনিক ডিক্রিজিং)।
- অ্যারে দুইবার ট্রাভার্স করুন (
i = 0 to 2n-1), ইন্ডেক্স =i % n। - যখন
nums[stack.top()] < nums[idx], তখনres[stack.top()] = nums[idx]এবং পপ করুন। - কারেন্ট ইন্ডেক্স পুশ করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
void printVec(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << v[i] << (i+1==v.size()?"":", ");
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;
while (!st.empty() && nums[st.top()] < nums[idx]) {
res[st.top()] = nums[idx];
st.pop();
}
st.push(idx);
}
return res;
}
};
int main() {
Solution ob;
vector<int> v = {1, 2, 1, 3, 2, 1};
printVec(ob.nextGreaterElements(v));
return 0;
}
ইনপুট
[1,2,1,3,2,1]
আউটপুট
[2, 3, 3, -1, 3, 2]
