सी++ में 132 पैटर्न

मान लीजिए कि हमारे पास n पूर्णांक a1, a2, ..., a का एक क्रम है, एक 132 पैटर्न एक अनुवर्ती ai, aj, ak है जैसे कि i

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=अंकों का आकार, यदि n 0 है, तो झूठी वापसी करें

• आकार n के minVals नामक एक सरणी को परिभाषित करें, minVals[0] :=nums[0]

  सेट करें

• 1 से n - 1 की सीमा में I के लिए

  • minVals[i] :=न्यूनतम minVals[i - 1] और nums[i]

• स्टैक सेंट बनाएं

• मैं के लिए n - 1 से नीचे 1 तक की श्रेणी में हूं

  • minVal :=minVals[i – 1]

  • वक्र:=अंक [जे]

  • जबकि सेंट खाली नहीं है और ढेर के ऊपर <=minVal

    . है

    • स्टैक सेंट से हटाएं

  • यदि सेंट खाली नहीं है और स्टैक के ऊपर

  • nums[i] s में डालें

• झूठी वापसी

उदाहरण (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