原题

LintCode 636. 132 Pattern

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.

n will be less than 20,000.

Example

Given nums = [1, 2, 3, 4]
return False // There is no 132 pattern in the sequence.

Given nums = [3, 1, 4, 2]
return True // There is a 132 pattern in the sequence: [1, 4, 2].

解题

题意为从数组中找依次出现的三个数（不一定相邻），使得这三个数中中第一个数字最小，第二个数字最大，第三个数字居中。

朴素的算法是：
首先定义较小的数为，一个数比它后面的那个数要小。（较大的数同理）
从头开始是寻找，从头开始找一个较小的数A，然后从A之后找一个较大的数B，最后看是否能在B之后找到一个数C，使得 B > C > A。
如果没找到就从B之后重新找A，继续开始。

利用栈的算法：
首先维护一个栈和一个变量C，然后从数组的最后往前遍历。当遇到一个值B比栈顶的值要大时，将所有比这个值小的数从栈中弹出，并将弹出的值中其中一个赋值给C，然后将B压入栈中。这样维护下去，结果就是，栈中的值都是比C要大的，且栈中的值在数组中出现的位置，都在C的前面。即这时候已经在数组中找到了BC，其中B > C，就差A了。此时只要遍历到一个值小于C，这个值就可以成为A。此时ABC三个值都找到了，且B > C > A，并且B的位置在C之前，A的位置在B之前，满足条件。

代码

class Solution {
public:
    /*
    * @param nums: a list of n integers
    * @return: true if there is a 132 pattern or false
    */
    bool find132pattern(vector<int> &nums) {
        if (nums.size() < 3) return false;
        // write your code here
        stack<int> s;
        int third = INT_MIN;
        auto it = nums.rbegin();
        while (it != nums.rend()) {
            if (third > *it) return true;
            else while (!s.empty() && *it > s.top()) {
                third = s.top();
                s.pop();
            }
            s.push(*it);
            it++;
        }
        return false;
    }
};