leetcode456.132模式_输入一个整数序列:a1, a2, ..., an,一个132模式的子序列ai, aj, ak被定义为

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