题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
大睿-SCTrojan 发布于 2016年2月19日 07:41 #
好奇的问一下,如果是k-tuplet咋办,用priority_queue吗?
在线疯狂 发布于 2016年2月19日 21:52 #
推广到k个,可以参考最长递增子序列的n*logn解法 http://bookshadow.com/weblog/321/
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.
在线疯狂 发布于 2016年3月19日 16:51 #
感谢补充!:D