Description
Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Answer
The 132 sequence needs three integers: the smallest integer, the largest integer, and a middle one. So we can use a integer a3 to store the largest integer in the sequence and a stack to store the middle integers, can parse all the integer in the given list to find the satisfied smallest integer. Since the integers in stack are definitely smaller than a3 , so we only need to find a number which is smaller than a3 .
Code
C++
class Solution {
public:
bool find132pattern(vector<int>& nums) {
if(nums.size() < 3) return false;
int n = nums.size();
stack<int> s;
int a3 = INT_MIN;
for(int i = n - 1; i >= 0; --i)
{
if(nums[i] < a3) return true;
while(!s.empty() && nums[s.top()] < nums[i])
{
int cur = s.top();
s.pop();
a3 = max(a3, nums[cur]);
}
s.push(i);
}
return false;
}
};
