leetcode 456 132 Pattern
z

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:

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

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

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

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

1
2
3
4
5
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].

  • 从右到左遍历
  • 使用一个stack来保存数据
  • 每当有一个数大于stack中最末尾的数时,popstack直到stack中末尾的数大于当前数
  • 把当前数放入stack
  • 如果当前数小于stack中的末尾的数时,直接pop进stack中

这样一来stack中保持降序排列,每次有一个数大于stack最末尾的数时,我们找到这些降序排列的数中,最大的一个小于当前数的数,标记为samllest。

所以,当有一个数小于smallest时,栈中肯定有一个数大于samllest。这样就说明存在132模式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
import sys
smallest = -sys.maxint
stack = []
for i in nums[::-1]:
if i < smallest:
return True
else:
while stack and i > stack[-1]:
smallest = stack.pop()
stack.append(i)
return False