首页 > 代码库 > 334. Increasing Triplet Subsequence
334. Increasing Triplet Subsequence
https://leetcode.com/problems/increasing-triplet-subsequence/#/description
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
.
Sol:
Start with the maximum numbers for the first and second element. Then:
(1) Find the first smallest number in the 3 subsequence
(2) Find the second one greater than the first element, reset the first one if it‘s smaller
class Solution(object): def increasingTriplet(self, nums): """ :type nums: List[int] :rtype: bool """ # Time O(n) SpaceO(1) if len(nums) < 3: return False first = second = float(‘inf‘) for n in nums: if n <= first: first = n elif n <= second: second = n else: return True return False
334. Increasing Triplet Subsequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。