目的：

给出一组数字，判断该数组中是否含有132模式的串，132模式，即存在i，j，k，均为数组的下标，且i < j < k，而对应的数字A_i，A_j，A_k，有关系A_i < A_k < A_j。

 

思路：

因为存在i < j < k，这一关系，所以我们从后开始遍历数组，就能保证这个条件成立。

我们用一个变量s3来记录可能的A_k，然后我们每遍历到一个数字，判断其是否小于s3，如果小于则满足A_i < A_k的关系。

而s3的来源是什么呢？我们使用一个栈，用来记录下当前第i个数字的后面所以可能为A_j的数字。

即当遍历到的数字大于等于s3（即不为A_i，有机会为A_j），这时我们判断该数字与栈顶元素的大小关系，若栈不为空且该数字比栈顶元素大，将栈顶元素出栈并把出栈的元素赋值到s3，直到栈为空或该数字比栈顶元素小。然后将该数字入栈。

所以刚入栈的数字与s3天然就有s3 < A_j。这时，遍历下一个，而刚遍历到的A_i，如果其小于s3，则满足A_i < A_k的关系。所以就有关系A_i < A_k < A_j。

 

代码：

1 class Solution { 2 public: 3     bool find132pattern(vector
     
      & nums) { 4         int len = nums.size(); 5         int s3 = INT_MIN; 6         stack
      
        st; 7         for (int i = len - 1; i >= 0; i--) { 8             if (nums[i] < s3) return true; 9             else {10                 while (!st.empty() && nums[i] > st.top()) {11                     s3 = st.top();12                     st.pop();13                 }14             }15             st.push(nums[i]);16         }17         return false;18     }19 };