334.md

334 Increasing Triplet Subsequence

Description

link

---

Solution

• Binary Search

看穿这道题的本质就是在于每来一个新的数字的时候怎么对dp数组中现有的已经是递增数组进行更新，两种情况，一种大于最大值，直接在数组后面加上这个数字，另一种在数组中间，那么第一个大于它的数字可以变成它，保证了后面如果有出现更合理数组的时候会一直更新下去，非常巧妙

---

Code

O(n) - O(1)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if not nums:
            return False
        dp = [nums[0]]
        for num in nums[1:]:
            if len(dp) == 2:
                if num > dp[1]:
                    return True
                elif num > dp[0]:
                    dp[1] = num
                else:
                    dp[0] = num
            else:
                if num > dp[0]:
                    dp.append(num)
                else:
                    dp[0] = num
        return False