132 Pattern

题目来源
给一个数组，判断数组中是否存在132模式的三个元素。
我一开始想着n方的方法，就是遍历一遍，然后每次从左找比当前元素小的，从右开始找比当前元素大的。代码如下：

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        for (int i=2; i<n; i++) {
            int l = 0, r = i - 1;
            while (l < r) {
                if (nums[l] < nums[i] && nums[r] > nums[i]) {
                    return true;
                }
                if (nums[l] >= nums[i])
                    l++;
                if (nums[r] <= nums[i])
                    r--;
            }
        }
        return false;
    }
};

然后就超时了==，然后看了下tags，里面写着栈！
然后还是没想出来怎么做，看了下讨论区，
实际上就是从后往前遍历，存储着一个栈，栈中元素都比当前值大，假如比当前元素小的话，那么就退栈，然后当前元素进栈。
然后s3是最后一个退栈的元素。
遍历的时候比较当前元素和s3的大小。
维持栈顶元素大于s3，并且序列栈顶元素小于s3。

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int s3 = INT_MIN;
        int n = nums.size();
        stack<int> s;
        for (int i=n-1; i>=0; i--) {
            if (nums[i] < s3)
                return true;
            else {
                while (!s.empty() && nums[i] > s.top()) {
                    s3 = s.top();
                    s.pop();
                }
                s.push(nums[i]);
            }
        }
        return false;
    }
};