LintCode 636. 132 Pattern

原題
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].
問題を解く
配列から順番に現れる3つの数(必ずしも隣接していない)を探して、この3つの数の中で最初の数字が最小で、2番目の数字が最大で、3番目の数字が中央になるようにします.
素朴なアルゴリズムは、まず小さい数を定義し、1つの数が後ろの数より小さいことです.(大きな数は同じです)最初から探して、最初から小さい数Aを探して、それからAの後から大きい数Bを探して、最後にBの後に1つの数Cを見つけることができるかどうかを見て、B>C>Aになります.見つからなかったらBの後からAを探し直して、続けます.
スタックのアルゴリズムを利用する:まず1つのスタックと1つの変数Cを維持し、それから配列の最後から前へ遍歴する.1つの値Bがスタックトップの値よりも大きい場合、この値よりも小さいすべての数をスタックからポップアップし、ポップアップされた値のうちの1つをCに割り当て、Bをスタックに押し込む.このように維持すると、結果として、スタック内の値はCよりも大きく、スタック内の値が配列に現れる位置は、Cの前にある.すなわち,このときすでに配列にBCが見つかっており,そのうちB > CはA差である.このとき,Cより小さい値まで遍歴すれば,この値はAとなる.このとき、ABCの3つの値が見つかり、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 &nums) {
        if (nums.size() < 3) return false;
        // write your code here
        stack 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;
    }
};