leetcode_334

发表于   |   分类于

Increasing Triplet Subsequence

题目戳这

题意

给定一个数组arr，问是否存在长度为3的子序列，使得arr[i] < arr[j] < arr[k],其中0<=i<j<k<=arr.length-1。

解法

用两个变量x1,x2来存储当前的最小值和次小值，如果碰到一个x>x1且x>x2了，那么说明就有长度为3的序列使得arr[i]<arr[j]<arr[k]了。

比如[1,7,4,5], 那么就是x1=1,x2=4,当数组循环到5的时候，就可以返回True。

我们要深刻理解x1和x2的概念，比如数组[1,2,0,3],当循环到3的时候，x1=0,x2=2的，那么此时还是成立的，因为x1代表的意思就是长度为1的序列的最小结尾数字，x2代表的意思就是长度为2的序列的最小的结尾数字。。这个有点像什么算法，，一下子想不起来名字了。。代码虽简单，但是想法还是比较巧妙的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        x1 = 0x7fffffff
        x2 = 0x7fffffff
        for x in nums:
            if x<=x1:
                x1 = x
            elif x<=x2:
                x2 = x
            else:
                return True
        
        return False