题目描述：

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 < k ≤ n-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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

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