leetcode 456 132 Pattern
z
 2019-06-10 15:36:04  

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