这是我在搜索 trie tree 的时候弹出来到一个题，乍一看觉得挺简单，但是对时间和空间都有要求，我能想到到办法就是以每个数为第一个数开始向后搜索，但是这样肯定不符合要求，于是看了评论区：Python-Easy-O(n)-Solution，惊为天人
思路如下：建立两个非常大的数，然后遍历数组并比较大小，如果遇到更小的就替换，如果能遇到比 first 和 second 都更大的数的话那就数 True
对于评论区提到的对数组 [1 5 5 0 0 0 8] 不满足的情况，其实仔细思考一下就知道肯定是满足的，因为当遍历到8的时候，first=0 且 second=5，虽然 [0 5 8] 不是一个满足条件的序列，但是由于 second=5，代表着在这个 5 之前，一定还有一个比 5 更小的数，不管他是多少，反正肯定能成为一个增加的序列
Explain
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
Solve
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first = second = float('inf')
for n in nums:
if n <= first:
first = n
elif n <= second:
second = n
else:
return True
return False
Performance
Python 的性能测试没有什么参考价值，以后都分析一下就行
在这个解法里，空间复杂度 O(1)，时间复杂度 O(n)，因为肯定需要遍历一遍数组，但是额外的空间只有 first 和 second