题目
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?
解题思路
确定Aj，在0-Aj-1找到一个小于Aj的数，在Aj+1到n找到一个小于A的数，使用前缀最小值数组，这样当确定Aj之后，就可得到0-Aj-1中最小的数（M0）。 从后遍历数组，当前数为Aj，并维护一个递减的单调栈，如果小于等于M0就pop出栈，这时如果栈中存在一个比Aj小的数，就存在132pattern
代码
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
l = len(nums)
if l <= 2:
return False
premin = [nums[0]]
for n in nums[1:]:
premin.append(min(premin[-1], n))
stack = []
for i in range(l - 1, -1, -1):
if nums[i] > premin[i]:
while stack and stack[-1] <= premin[i]:
stack.pop()
if stack and stack[-1] < nums[i]:
return True
stack.append(nums[i])
return False
