根据题意,对于 0 < i < n -1 的 nums[i] 存在 nums[k] < nums[i], 0 <= k < i 且 nums[j] < nums[i], i < j < n 则设置 左右数组 l, r 其中 l[i] 表示 i 左侧比 nums[i] 小的最小值, r[i] 表示 i 右侧比 nums[i] 小的最大值,即只要在 0 < i < n - 1 时,l[i] < r[i] 即满足条件
代码如下:
class Solution: def find132Subseq(self , nums: List[int]) -> bool: # write code here l, r = [float("inf") for _ in range(len(nums))], [float("-inf") for _ in range(len(nums))] l[0], r[-1] = nums[0], nums[-1] for i in range(1, len(nums)): if nums[i] > nums[i - 1]: l[i] = min(l[i - 1], nums[i - 1]) for i in range(len(nums) - 2, -1, -1): if nums[i] > nums[i + 1]: r[i] = max(r[i + 1], nums[i + 1]) for i in range(1, len(nums) - 1): if l[i] < r[i]: return True return False