本文共 859 字,大约阅读时间需要 2 分钟。
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.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]Output: true
Example 2:
Input: [5,4,3,2,1]Output: false
找到是否存在三个递增的数(不一定挨着)。
看到一个思路很巧妙,设置了first和second两个数,表示从前到后遍历的时候,递增的最小的两个数。
这样即使出现了更小的数字,改变了first,也不会改变second,所以出现一个大于second的数的时候还是能return True
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: first=second=float('inf') for num in nums: if num<=first: first=num elif num<=second: second=num else: return True return False
转载地址:http://njrbb.baihongyu.com/