334.md

解法一

• 60ms
• 64%

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        maxIdx = 0
        for val in nums:
            cur = self.lower_bound(nums,0,maxIdx,val)
            nums[cur] = val
            if cur == maxIdx:
                maxIdx += 1
                if maxIdx>=3: return True
            # print(cur, val, nums[0:maxIdx])
        return False
    def lower_bound(self, nums, l, r, key):
        while l < r:
            mid = (l+r)>>1
            if nums[mid] < key: l = mid+1
            else: r = mid
        return l

解法二

维护一个二元升序子序列，即使用一个变量small，和一个变量big。遍历数组：

• 如果一个数小于或等于small，则更新small
• 如果大于small，但是小于等于big，则更新big
• 如果大于big，那么就找到一个三元升序子序列

这个地方可能不太好理解的是：如果在更新完small后，出现了一个大于big的数，那么判断为找到了一个三元升序子序列。这种情况下，big的最后一次更新在small前，small，big和最后大于big的这个数的位置顺序是：big,small,大于big的数。这个顺序不是一个三元升序序列，但是我们判断结果是找到了三元升序子序列，这个解决是对的，但是上面这3个数并不是正确的升序序列

几个例子，假设初始数组如下：

2,3,1,4

处理到3时：

small = 2
big = 3

处理1。因为1小于small，所以更新small：

small = 1
big = 3

处理4。因为4大于big，所以判断为找到了三元升序子序列

此时3个数为1,3,4，但是在数组中对应的顺序是3,1,4。那为什么结果是对的？因为我们判断为true的条件是是：找到一个大于big的数。因为当找到一个大于small的数时，才会更新big，虽然这里最后更新了small，但是在最后一次更新big之前，肯定更新过small，所以数组中确实是存在升序的三元子序列。也就是说，真正的三元升序子序列是2,3,4

• 56ms
• 80%

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums)<3: return False
        small, big = float("inf"), float("inf")
        for val in nums:
            if val <= small: small = val
            elif val<=big: big = val
            else: return True
        return False

解法三

• 56ms
• 80%

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums)<3: return False
        i, j, k = 0,1,2
        while k < len(nums):
            if nums[i] < nums[j] and nums[j] < nums[k]:
                return True
            while nums[j] <= nums[i]:
                i = j
                j,k = i+1,i+2
                if k>len(nums) - 1: return False
            while nums[k] <= nums[j]:
                k+=1
                if k > len(nums)-1:
                    j,k = j+1, j+2
                    break
        return False