题目
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.
题意
给定一个无序数组，数组中是否有超过三个元素的递增序列（不一定连续）
例子
Input: [1,2,3,4,5]
Output: true
题解
前阵子刚做的第300题，那道题求的是最长递增子序列长度。那道题最快是使用dp数组，对每个元素在dp中进行二分查找。找出第一个大于他的元素并替换，没有则插入dp数组。依次来获得最长。即dp[i]表示的是下标为i的位置时最长递增序列长度。这里只要能求出dp长度为3即可。时间复杂度为O(nlog)
但是这道题要求时间复杂度为O(1),所以上述思路显然无法达到要求。
可以考虑这道题的特点是长度为3，所以我们可以设置两个指针min1,min2，两个指针指向的元素递增。首先设置他们为最大值，然后遍历数组，
如果nums[i]<min1,则min1=nums[i];
如果min1<nums[i]<min2,则min2=nums[i]；
如果nums[i]>min2>min1,则返回true;
代码
func increasingTriplet(nums []int) bool {
min1,min2:= 2<<32-1,2<<32-1
for _,v:=range nums{
if v<=min1{
min1=v
}else if v<=min2{
min2=v
}else {
return true
}
}
return false
}
总结
这道题的方法需要点小技巧吧。一开始是由想过用指针。但是陷入到dp中，然后就走不出来了。。因为长度为3，所以可以用两个指针。感觉这在很多题目都可以适用。
