abstract：Leetcode[132] PatternGiven 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 o

Leetcode[132] Pattern

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].

Stack

復(fù)雜度
O(N),O(N)

思路
維護(hù)一個(gè)pair, 里面有最大值和最小值。如果當(dāng)前值小于pair的最小值，那么就將原來的pair壓進(jìn)去棧，然后在用這個(gè)新的pair的值再進(jìn)行更新。如果當(dāng)前值大于pair的最大值，首先這個(gè)值和原來在stack里面的那些pair進(jìn)行比較，如果這個(gè)值比stack里面的值的max要大，就需要pop掉這個(gè)pair。如果沒有適合返回的值，就重新更新當(dāng)前的pair。

代碼

Class Pair {
    int min;
    int max;
    public Pair(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

public boolean find123Pattern(int[] nums) {
    if(nums == null || nums.length < 3) return false;
    Pair cur = new Pair(nums[0], nums[0]);
    Stack<Pair> stack = new Stack<>();
    for(int i = 1; i < nums.length; i ++) {
        if(nums[i] < cur.min) {
            stack.push(cur);
            cur = new Pair(nums[i], nums[i]);
        }
        else if(nums[i] > cur.max) {
            while(!stack.isEmpty() && stack.peek().max <= nums[i]) {
                stack.pop();
            }
            if(!stack.isEmpty() && stack.peek.max > nums[i]) {
                return true;
            }
            cur.max = nums[i];
        }
        else if(nums[i] > cur.min && nums[i] < cur.max) {
            return true;
        }
    }
    return false;
}