递增的三元子序列

元子序列"/>

递增的三元子序列

给你一个整数数组 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

代码：

class Solution:

    def increasingTriplet(self, nums: List[int]) -> bool:

        small = mid = inf

        for num in nums:

            if num <= small:

                small = num

            elif num <= mid:

                mid = num

            else:

                return True

        return False

思路解析：

在求解LIS（最长上升子序列时，我们常用单调栈维护+二分查找实现）。 本题只需要找到任意一个长度等于3的上升子序列，故可以用两个变量模拟前两个栈内元素， 判断当前数字在跟这两个元素的大小关系，如果小于第一个，则替换第一个，然后如果小于第二个，则替换第二个，否则我们已经找到了满足答案的三个数。