Python｜Leetcode《334》｜递增的三元子序列

一、题目描述

题目：递增的三元子序列

难度：中等

地址：《递增的三元子序列》

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

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

示例1

输入：nums = [1,2,3,4,5]

输出：true

解释：任何 i < j < k 的三元组都满足题意

示例2

输入：nums = [5,4,3,2,1]

输出：false

解释：不存在满足题意的三元组

示例3

输入：nums = [2,1,5,0,4,6]

输出：true

解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

二、题目解析

注：本题博主乍一看以为是连续的递增序列（如果是会简单许多），实则不然，这里要注意。

题中需要我们找到整个数组中是否含有递增的三元子序列，解题思想如下：

1.定义前两个数为极限（或者超过约束范围的数）

2.遍历数组中的所有数据使用三重判断进行三个数的判断（if…elif…else）

1.if： 如果遍历到的数字小于第一个数字，则替换第一个数字；

2.elif：如果遍历到的数字大于第一个数字且比第二个数字小，则替换第二个数字（任何一次替换都证明此时已经有了递增的2元子序列），否则第二个数永远为inf；

3.else：如果遍历到的数字大于第一个和第二个数字，证明此时存在递增的3元子序列。

三、解题代码

解法（一）

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