Skip to content

334 increasing triplet subsequence

334. Increasing Triplet Subsequence

题目: https://leetcode.com/problems/increasing-triplet-subsequence/

难度: Medium

思路:

用longest increasing subsequence来求,超时

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums: return False
        n = len(nums)
        dp = [1 for i in range(n)]
        for i in range(1,n):
            for j in range(i):
                if nums[i] > nums[j] :
                    dp[i] = max(dp[i],dp[j] + 1)
                    if dp[i] >= 3:
                        return True

        return False

于是转而用Third Maximum Number的方法,维护一个当前最小和当前第二小,当碰到当前比较大,返回True,否则一圈走下来依旧不能满足,返回false.

想一下,如果不是求三个增长,如果是求两个的话,那么一定想到的是保存当前最小值,那么一旦后方遇到一个比较大的,就这样处理掉了。

所以对于任何一个num来说,有三种可能:

  • 小于当前的最小值,那么更新当前最小值
  • 小于当前第二小值,更新当前第二小值
  • 如果以上两种都不是,那么是大于当前第二小值和最小值,于是这样就true

所以是求四个增长也是类似的么

AC代码

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # m - min, sm - second min
        m, sm = float('inf'), float('inf')

        for num in nums:
            print m, sm
            if m >= num:
                m = num
            elif sm >= num:
                sm = num
            else:
                return True
        return False


回到顶部