C++ এ 132 প্যাটার্ন

ধরুন আমাদের n পূর্ণসংখ্যার একটি ক্রম আছে a1, a2, ..., an, a 132 প্যাটার্ন হল একটি পরবর্তী ai, aj, ak যাতে i

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

• n :=সংখ্যার আকার, যদি n 0 হয়, তাহলে মিথ্যা ফেরত দিন

• n আকারের minVals নামক একটি অ্যারে সংজ্ঞায়িত করুন, minVals[0] সেট করুন :=সংখ্যা[0]

• আমি 1 থেকে n – 1

  রেঞ্জে

  • minVals[i] :=সর্বনিম্ন minVals[i - 1] এবং সংখ্যা[i]

• স্ট্যাক স্ট্যাক তৈরি করুন

• আমি n – 1 থেকে 1

  রেঞ্জে

  • minVal :=minVals[i – 1]

  • curr :=সংখ্যা[j]

  • যখন st খালি নয় এবং স্ট্যাকের উপরের অংশটি <=minVal

    • স্ট্যাক st

      থেকে মুছুন

  • যদি st খালি না হয় এবং স্ট্যাকের উপরে

  • s

    -এ nums[i] সন্নিবেশ করান

• ফেরত মিথ্যা

উদাহরণ (C++)

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

-->

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool find132pattern(vector<int>& nums) {
      int n = nums.size();
      if(!n) return false;
      vector <int> minVals(n);
      minVals[0] = nums[0];
      for(int i = 1; i < n; i++){
         minVals[i] = min(minVals[i - 1], nums[i]);
      }
      stack <int> s;
      for(int i = n - 1; i > 0; i--){
         int minVal = minVals[i - 1];
         int curr = nums[i];
         while(!s.empty() && s.top() <= minVal) s.pop();
         if(!s.empty() && s.top() < curr) return true;
         s.push(nums[i]);
      }
      return false;
   }
};
main(){
   vector<int> v = {-1,3,2,0};
   Solution ob;
   cout << (ob.find132pattern(v));
}

ইনপুট

[-1,3,2,0]

আউটপুট

1