力扣 456. 132模式 枚举 二分 贪心 单调栈

https://leetcode-cn.com/problems/132-pattern/

思路一：枚举位置$j$，根据贪心思想，$a_i$自然要取左侧最小的那个值，那么假设我们有一个数据结构可以维护有序的元素，删除、插入、查询的复杂度都是$log(n)$，这个问题就解决了。在右侧待选数据中二分找到$>a_i$的最小的数，再看其与$a_j$关系即可。

from sortedcontainers import SortedListclass Solution:def find132pattern(self, nums: List[int]) -> bool:n=len(nums)if n<3:return Falseleft_min=nums[0]j=1right_list=SortedList(nums[2:])while j<n-1:if nums[j]<=left_min:left_min=nums[j]else:# 找到右侧所有数据中大于left_min的第一个数据的下标index=right_list.bisect_right(left_min)if index<len(right_list) and right_list[index]<nums[j]:return Truej+=1right_list.remove(nums[j])return False

思路二：单调递减栈从右向左维护待选的$a_k$，当遇到大于栈顶的元素时，可以把它当作待选的$a_j$，不断弹出栈顶找到最大的$<a_j$的$a_k$，下一步只要判断是否有合适的$a_i$即可。

from sortedcontainers import SortedListclass Solution:def find132pattern(self, nums: List[int]) -> bool:n=len(nums)if n<3:return Falsestk=[nums[n-1]]maxk=float("-inf")for i in range(n-2,-1,-1):if nums[i]<maxk:return Truewhile len(stk)>0 and nums[i]>stk[-1]:maxk=stk[-1]stk.pop()if nums[i]>maxk:stk.append(nums[i])return False