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

解题思路

• 定义一个栈，倒序遍历存储一个新数的时候，弹出里面所有比它小的数字。弹出的这些数就会成为s3的可能选择，记为min

• 我们维护s3的最大选择（它一定是从栈中最后一个被弹出的数字）；

• 一旦我们遇到一个比s3小的数，就说明我们找到了合法的序列s1 < s3。由于s2 > s3，所以一定可以推导出s1 < s2。

代码如下：

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    if (nums.length < 3) return false;
    
    var stack = [];
    var min = -Infinity;
    
    for (var i=nums.length-1; i>=0;i--) {
        if (nums[i] < min) return true;
        
        while (stack.length>0 && nums[i]> stack[stack.length-1]) {
            min = stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
};

时间复杂度：O(n)
空间复杂度：O(n)