题目描述

给定一个未排序的数组，请判断这个数组中是否存在长度为3的递增的子序列。

正式的数学表达如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。

要求算法时间复杂度为O(n)，空间复杂度为O(1) 。

示例: 输入 [1, 2, 3, 4, 5], 输出 true.

输入 [5, 4, 3, 2, 1], 输出 false.

最优解法——记忆搜索类DP（AC）

保留了此前两个比较状态在 first 和 second 两个变量之中，第三个最大数只和第二个存储变量进行对比即可。
在循环中不断用比first小的数覆盖first，用小于second、大于first的数覆盖second，遇到比second大的数直接返回True。
时间复杂度O(n)，空间复杂度O(1)
Beat 67%

class Solution:
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        length = len(nums)
        if(length < 3):
            return False
        first = nums[0]
        second = None
        
        for i in range(1,length):
            if(nums[i] <= first):
                first = nums[i]
            else:
                if((second is None and nums[i] > first) or (second is not None and nums[i] <= second)):
                    second = nums[i]
                else:
                    return True
        print(str(first) + str(second))
        return False