描述：给你一个 n 个整数的序列 a1,a2,...,an，一个 132 模式是对于一个子串 ai,aj,ak，满足 i < j < k 和 ai < ak < aj。设计一个算法来检查输入的这 n 个整数的序列中是否存在132模式。
n 会小于 20,000。
思路：维护一个栈和一个变量third，其中third就是第三个数字，也是pattern132中的2，栈里面按顺序放所有大于third的数字，也是pattern132中的3，那么我们在遍历的时候，如果当前数字小于third，即pattern 132中的1找到了，我们直接返回true即可,倒序遍历依次更新st,thrid值
注意事项：i,j,k可以是不连续的
class Solution {
public:
/**
* @param nums: a list of n integers
* @return: true if there is a 132 pattern or false
*/
bool find132pattern(vector<int> &nums) {
// write your code here
int len = nums.size();
if( len < 2 )
{
return false;
}
std::stack<int> st;
int thrid = INT_MIN;
for( int i = len - 1; i >= 0; --i)
{
if( nums[i] < thrid )
{
return true;
}
while( !st.empty() && nums[i] > st.top() )
{
thrid = st.top();
st.pop();
}
st.push(nums[i]);
}
return false;
}
};
