मान लीजिए हमारे पास n इंटीजर्स का एक सीक्वेंस a1, a2, ..., an है, एक 132 पैटर्न एक सबसीक्वेंस ai, aj, ak है जैसे कि i < j < k और ai < ak < aj। तो हमें एक एल्गोरिदम डिजाइन करना है जो n नंबर्स की एक लिस्ट को इनपुट के रूप में लेता है और जांचता है कि क्या लिस्ट में 132 पैटर्न है। उदाहरण के लिए, अगर इनपुट है [-1, 3, 2, 0], तो आउटपुट true होगा, क्योंकि तीन पैटर्न हैं [-1, 3, 2], [-1, 3, 0] और [-1, 2, 0]।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
n := nums का साइज, अगर n 0 है, तो false लौटाएं
minVals नाम का एक ऐरे डिफाइन करें जिसका साइज n हो, minVals[0] := nums[0] सेट करें
i को 1 से n-1 तक लूप करें:
minVals[i] := minVals[i-1] और nums[i] का मिनिमम
एक स्टैक st बनाएं
i को n-1 से 1 तक डाउनटू लूप करें:
minVal := minVals[i-1]
curr := nums[i]
जब तक st खाली नहीं है और स्टैक का टॉप <= minVal:
स्टैक से डिलीट करें
अगर st खाली नहीं है और स्टैक का टॉप < curr, तो true लौटाएं
nums[i] को st में इंसर्ट करें
false लौटाएं
उदाहरण (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;
}
};
int main(){
vector<int> v = {-1,3,2,0};
Solution ob;
cout << (ob.find132pattern(v));
}
इनपुट
[-1,3,2,0]
आउटपुट
1
