leetcode 递增的三元子序列 python

维护一组cp，存放当前最合适的前两个。
1.如果当前读到的数，比第二个还大，输出True。
2.如果比第二个小，比第一个大，更新第二个为当前的数。
3.如果当前数比第一个小，更新第一个为当前数。

对于例子[2,3,1]
如果依照规则3，会找到[1,3]这样一个子序列，这明显是错的，但是却不影响最终的结果。（我们只关心当前是否有长度为2的序列，第二个数是多少，而第一个数是多少是不关心的）

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums)<3:
            return False
        
        best_cp=[float("inf"),float("inf")]
        
        for num in nums:
            if num > best_cp[1]:
                return True            
            
            if num<best_cp[0]:
                best_cp[0]=num
                continue
            
            if num>best_cp[0] and num<best_cp[1]:
                best_cp[1]=num
        return False

穷举法（不符合要求）：

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums)==0:
            return False
        for i1 in range(len(nums)-2):
            if nums[i1]>nums[i1+1]:
                continue
            for i2 in range(i1+1,len(nums)):
                if nums[i2]<=nums[i1]:
                    continue
                for i3 in range(i2+1,len(nums)):
                    if nums[i3] >nums[i2]:
                        return True
        return False

维护两个cp，一个表示当前最好的cp，一个表示可能取代它的cp。分了很多情况，但总算是搞定了。

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        best_cp=[None,None]
        cur_cp=[None,None]
        
        for num in nums:
            #print(num)
            #print(best_cp)
            #print(cur_cp)
            if best_cp[0] is None:
                best_cp[0]=num
                continue
            if best_cp[1] is None:
                if num<best_cp[0]:
                    best_cp[0]=num
                if num>best_cp[0]:
                    best_cp[1]=num
                continue
            if num > best_cp[1]:
                return True
            
            if num == best_cp[1]:
                continue
            
            if num > best_cp[0]:
                best_cp[1]=num
                continue
            
            if cur_cp[0]==None:
                cur_cp[0]=num
            
            if num<cur_cp[0]:
                cur_cp[0]=num
            if num>cur_cp[0]:
                cur_cp[1]=num
            
            if cur_cp[1] is not None:
                if cur_cp[1] < best_cp[1]:
                    best_cp=cur_cp[:]
                else:
                    cur_cp[:]=[None,None]