Problem

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• -10^9 <= nums[i] <= 10^9

Example1

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example2

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example3

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Solution

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> stk;
        int right = INT_MIN; //最大的满足要求的数的最大值。要求就是其左侧存在一个比它大的数。

        for(int i = nums.size() -1 ;i >= 0;--i)
        {
            if(nums[i] < right)
                return true;
            while(stk.size() && nums[i] > stk.top())
            {
                right = max(right,stk.top());
                stk.pop();

            }

            stk.push(nums[i]);
        }

        return false;

    }
};