问题描述
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.
问题分析
设置两个变量m1、m2记录当前最小值和次小值，在新读入一个数字x时：
- x<=m1：更新m1=x；
- m1<x<=m2：更新m2=x；
- 出现m1<m2<x的情况，返回True。
这个算法的巧妙之处在于保证m1<m2，并且m1、m2的更新很有趣，使当前保存的m1、m2始终最有利于获得解。
AC代码
class Solution(object):
def increasingTriplet(self, nums):
if len(nums) < 3:
return False
m1 = m2 = max(nums) + 1
for num in nums:
if num <= m1:
m1 = num
elif num <= m2:
m2 = num
else:
return True
return False
Runtime: 48 ms, which beats 81.85% of Python submissions.
