leetcode 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:
1 | Input: [1, 2, 3, 4] |
Example 2:
1 | Input: [3, 1, 4, 2] |
Example 3:
1 | Input: [-1, 3, 2, 0] |
- 从右到左遍历
- 使用一个stack来保存数据
- 每当有一个数大于stack中最末尾的数时,popstack直到stack中末尾的数大于当前数
- 把当前数放入stack
- 如果当前数小于stack中的末尾的数时,直接pop进stack中
这样一来stack中保持降序排列,每次有一个数大于stack最末尾的数时,我们找到这些降序排列的数中,最大的一个小于当前数的数,标记为samllest。
所以,当有一个数小于smallest时,栈中肯定有一个数大于samllest。这样就说明存在132模式。
1 | class Solution(object): |