单调栈$O(n)$

class Solution {
public:
    bool find132pattern(vector<int>& a) {
        stack<int> stk;
        int right = INT_MIN;
        //right存的是a[k]（满足a[j] > a[k], j < k）
        //栈中元素一定大于right，所以只需判断nums[i]是否小于right
        for (int i = a.size() - 1; ~i; i --)
        {
            if (a[i] < right) return true;
            else 
            {
                //栈中应存最大值a[j], 若a[i] > a[j]，则需将a[j]更新为a[i]
                while (stk.size() && a[i] > stk.top())
                {
                    right = max(right, stk.top()); //right始终存次最大值
                    stk.pop();
                }
                stk.push(a[i]);
            }
        }
        return false;
    }
};