根据题意，对于 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

题解 | #132序列#

全站热榜