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

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

/

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

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+=ve(nums[j])return False

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

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