C++ এ একটি তালিকা সংখ্যা থেকে একটি ট্রিপলেট সংখ্যা[i]

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে, আমাদের পরীক্ষা করতে হবে সেখানে ট্রিপলেট (i, j, k) আছে কিনা যেমন i

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[2, 12, 1, 4, 4], তবে আউটপুটটি সত্য হবে, কারণ [2, 12, 4] মানদণ্ডের সাথে মেলে কারণ 2 <4 <12।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সংখ্যার আকার

• n

  আকারের বাম একটি অ্যারে সংজ্ঞায়িত করুন

• বাকি[0] :=সংখ্যা[0]

• আরম্ভ করার জন্য i :=1, যখন i

  • left[i] :=ন্যূনতম সংখ্যা[i] এবং বাম[i - 1]

• একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=n - 1, যখন i>=1, আপডেট করুন (i 1 দ্বারা কম করুন), করুন −

  • x :=বাম[i - 1]

  • যখন st খালি নয় এবং st <=x, do −

    • st

      থেকে পপ

  • যদি st খালি না হয় এবং x st এর উপরের, তাহলে −

    • প্রত্যাবর্তন সত্য

  • সংখ্যাগুলিকে [i] st

    -এ ঠেলে দিন

• মিথ্যা ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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;
   }
};
bool solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
int main(){
   vector<int> v = {2, 12, 1, 4, 4};
   cout << solve(v);
}

ইনপুট

{2, 12, 1, 4, 4}

আউটপুট

1