সমস্যা বিবরণ
একটি সংখ্যার তালিকা nums দেওয়া আছে। চেক করতে হবে কি এমন ট্রিপলেট (i, j, k) আছে যাতে i < j < k এবং nums[i] < nums[k] < nums[j]।
উদাহরণ: nums = [2, 12, 1, 4, 4] হলে আউটপুট True (১), কারণ [2, 12, 4] এর জন্য 2 < 4 < 12।
সমাধানের পদ্ধতি
left[i]অ্যারে তৈরি করুন যাতেleft[i] = min(nums[0...i])থাকে।- স্ট্যাক ব্যবহার করে ডান পাশ থেকে ট্রভার্স করুন।
- প্রতিটি
iএর জন্যx = left[i-1]নিন। - স্ট্যাকে থেকে
x-এর চেয়ে ছোট বা সমান উপাদান পপ করুন। - যদি স্ট্যাক খালি না হয় এবং
x < nums[i]এবংnums[i] > st.top()হয়, তবে ট্রিপলেট পাওয়া গেছে —trueরিটার্ন করুন। nums[i]স্ট্যাকে পুশ করুন।- শেষে
falseরিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
left[0] = nums[0];
for (int i = 1; i < n; i++)
left[i] = min(nums[i], left[i - 1]);
stack<int> st;
for (int i = n - 1; i >= 1; i--) {
int x = left[i - 1];
while (!st.empty() && st.top() <= x)
st.pop();
if (!st.empty() && x < nums[i] && nums[i] > st.top())
return true;
st.push(nums[i]);
}
return false;
}
};
int main() {
vector<int> v = {2, 12, 1, 4, 4};
cout << solve(v);
return 0;
}
ইনপুট ও আউটপুট
ইনপুট: {2, 12, 1, 4, 4}
আউটপুট: 1
