Increasing Triplet Subsequence
描述
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
More specifically, if there exists i
, j
, k
such that arr[i] < arr[j] < arr[k]
given 0 ≤ i < j < k ≤ n-1
return true
else return false
.
Your function should run in O(n)
time complexity and O(1)
space complexity.
Examples:
- Given
[1, 2, 3, 4, 5]
, returntrue
. - Given
[5, 4, 3, 2, 1]
, returnfalse
.
分析
扫描一遍数组,用变量x1
保存当前最小的值,变量x2
保存当前第二小的值。如果右面能碰到一个数大于x2
,说明必然存在一个递增的三元组。