मान लीजिए कि हमारे पास 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