1.题目描述

给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

注意：n 的值小于15000。

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。 示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2]. 示例 3:

输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

2.解决思路

数据结构：单调栈，维持一个数值递减的单调栈，栈顶元素最小

从后向前遍历，需要找到一个third，使得third<second，并且有更优的third>first，third是所有可选的third中最大的那个。

维持栈内的元素都比third大（站内元素代表second，second>third），如果来了一个元素比栈顶大，则弹出栈顶，把栈顶赋值给third，重复弹栈和赋值的操作直到当前元素比栈顶值小（寻找更优的third过程），再将该元素入栈

如果来了一个元素比third小，说明是first，first<third，直接返回true，如果该元素比栈顶小，将该元素入栈

如果最后都没有元素比third小，则返回false

3.代码实现

class Solution(object): def find132pattern(self, nums): """ :type nums: List[int] :rtype: bool """ if len(nums)<3: return False stack=[] third=-1000000000 for i in range(len(nums)-1,-1,-1): if nums[i]<third: return True while len(stack)!=0 and nums[i]>stack[-1]: third=stack.pop(-1) stack.append(nums[i]) return False