334 递增的三元子序列（动态规划-最长上升子序列）

1. 问题描述：

给你一个整数数组 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 <= nums.length <= 10 ^ 5
-2 ^ 31 <= nums[i] <= 2 ^ 31 - 1

进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence

2. 思路分析：

① 分析题目可以知道这道题目与力扣300题是类似的，我们只需要求解出给出数组的最长上升子序列的长度，判断最长上升子序列的长度是否大于等于3即可，所以就转变为求解给出数组中的最长上升子序列的长度问题。最长上升子序列可以由两种求解的方法，第一种是常规的动态规划求解，尝试将当前遍历的数字添加到之前的递增子序列的后面判断是否更长，如果更长那么更新以当前遍历的数字结尾的最长子序列的长度，时间复杂度为O(n ^ 2)，第二种是贪心 + 动态规划的思路，因为我们需要使得递增的子序列长度更长所以结尾的数字应该越小越好，所以dp[i]表示以当前长度为i结尾的最小数字，遍历当前数组判断当前的数组是否大于dp列表中的最后一个数字如果满足那么直接将其添加到后面即可，否则在dp列表中找到当前遍历的数字应该插入的位置，更新的目的是使得以当前长度为j的上升子序列结尾的数字更小这样就可能构成更长的上升子序列，因为dp列表是有序的所以使用二分查找的方法即可，最后dp列表的长度就是最长上升子序列的长度。

② 除了使用①中的最长上升子序列的思路我们还可以进一步优化代码，因为求解的只是长度为3的上升子序列，所以我们声明长度为2的列表来记录一下以当前长度为1,2的递增子序列结尾的最小数字即可。其实是①的简化版本。

3. 代码如下：

from typing import List


class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        # 可以使用O(nlgn)的时间复杂度解决
        dp = list()
        for n in nums:
            if not dp or dp[-1] < n:
                dp.append(n)
            else:
                # 二分查找当前数字应该插入的使得长度为j的递增子序列结尾的数字更小
                l, r = 0, len(dp) - 1
                loc = 0
                while l <= r:
                    mid = l + r >> 1
                    if n <= dp[mid]:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                dp[loc] = n
        return len(dp) >= 3

优化：

from typing import List
import sys

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        inf = sys.maxsize
        q = [inf] * 2
        for n in nums:
            k = 2
            while k > 0 and q[k - 1] >= n:
                k -= 1
            if k == 2: return True
            q[k] = n
        return False