Description

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.

Example 1:

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

Example 2:

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

Example 3:

Input: [-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

观察 “1 3 2”的结构，其中“3 2”是有序的，因此可以倒序遍历数组，始终维护两个数a和b，保证a>b的条件下使a b尽量大，左边到来的数小于b即找到了“1 3 2”结构，程序结束。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool find132pattern(vector<int>& nums) {
    int s2 = INT_MIN;
    stack<int> st;
    for(int i = nums.size() - 1; i >= 0; i--) {
        if (nums[i] < s2) return true;
        while (!st.empty() && nums[i] > st.top()) {
            s2 = st.top();
            printf("s2 = %d\n",s2);
            st.pop();
        }
        st.push(nums[i]);
        printf("push %d\n",nums[i]);
    }
    return false;
}