0%

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.

1
2
3
4
5
6
Example 1:
Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

1
2
3
4
5
6
7
8
9
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。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @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)