[LeetCode]Increasing Triplet Subsequence

题目描述:

LeetCode 334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < kn-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

题目大意:

给定一个无序数组,判断其中是否存在一个长度为3的递增子序列。

形式上,函数应当:

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

你的算法应当满足O(n)时间复杂度和O(1)空间复杂度。

测试用例如题目描述。

解题思路:

维护变量a, b,用来记录数组中大小递增的前2个元素。

更确切的说:a是当前的最小元素;b是位于a之后,大于a并且距离a最近的元素。

初始令a = b = None

遍历数组nums,记当前元素为n

  若a为空或者a >= n,则令a = n;

  否则,若b为空或者b >= n,则令b = n;

  否则,返回true

遍历结束时,返回false。

Python代码:

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        a = b = None
        for n in nums:
            if a is None or a >= n:
                a = n
            elif b is None or b >= n:
                b = n
            else:
                return True
        return False

问题的推广:

如果将本问题中递增子序列的长度从3推广到n,则可转化为求解最长递增子序列问题。

参阅 LeetCode 300:Longest Increasing Subsequence

本文链接:http://bookshadow.com/weblog/2016/02/16/leetcode-increasing-triplet-subsequence/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 大睿-SCTrojan 大睿-SCTrojan 发布于 2016年2月19日 07:41 #

    好奇的问一下,如果是k-tuplet咋办,用priority_queue吗?

  2. 在线疯狂 在线疯狂 发布于 2016年2月19日 21:52 #

    推广到k个,可以参考最长递增子序列的n*logn解法 http://bookshadow.com/weblog/321/

  3. ylf951 ylf951 发布于 2016年3月17日 08:42 #

    a is the minimum element so far, b is the element that is closest to a among all elements after and greater than a.

  4. 在线疯狂 在线疯狂 发布于 2016年3月19日 16:51 #

    感谢补充!:D

张贴您的评论