334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

十分钟写出来的费时费空间解法：

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        ## DP1 动态规划，定义第i个值为在这个数左边含这个数能达到的最小值
        dp1 = [nums[0]] * n
        for i in range(1,n):
            dp1[i] = min(dp1[i-1], nums[i])
        ## DP2 动态规划，定义第i个值为在这个数右边含这个数能达到的最大值
        dp2 = [nums[-1]] * n
        for i in range(n-2,-1,-1):
            dp2[i] = max(dp2[i+1], nums[i])
        
        for i in range(n):
            if nums[i] > dp1[i] and nums[i] < dp2[i]:
                return True
        return False

执行用时：224 ms, 在所有 Python3 提交中击败了7.07%的用户

内存消耗：27.5 MB, 在所有 Python3 提交中击败了5.12%的用户

其实也就是官方标答的双向遍历法：

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        leftMin = [0] * n
        leftMin[0] = nums[0]
        for i in range(1, n):
            leftMin[i] = min(leftMin[i - 1], nums[i])
        rightMax = [0] * n
        rightMax[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], nums[i])
        for i in range(1, n - 1):
            if leftMin[i - 1] < nums[i] < rightMax[i + 1]:
                return True
        return False

贪心算法：

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        first, second = nums[0], float('inf')
        for i in range(1, n):
            num = nums[i]
            if num > second:
                return True
            if num > first:
                second = num
            else:
                first = num
        return False

贪心算法比较巧的一点就是，出现第三个数的情况。基于第三个数一定会比第二个数小，所以可以取缔第二个数或者第一个数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。