Leetcode 456. 132 Pattern
文章作者:Tyan
博客:noahsnail.com | CSDN | 简书
1. Description
2. Solution
- Version 1
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int size = nums.size();
if(size == 0) {
return false;
}
int min = nums[0];
for(int j = 1; j < size - 1; j++) {
if(nums[j] > min) {
for(int k = j + 1; k < size; k++) {
if(nums[j] > nums[k] && min < nums[k]) {
return true;
}
}
}
else {
min = nums[j];
}
}
return false;
}
};
- Version 2
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int third = INT_MIN;
stack<int> s;
for(int i = nums.size() - 1; i >= 0; i--) {
if(nums[i] < third) {
return true;
}
while(!s.empty() && nums[i] > s.top()) {
third = s.top();
s.pop();
}
s.push(nums[i]);
}
return false;
}
};