Description:
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.
Example:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
Link:
https://leetcode.com/problems/increasing-triplet-subsequence/#/description
题目意思：
判断一个数组是否有递增的长度>=3的子集（顺序不变）。
解题方法：
因为需要O(n)的时候解决，所以求最长递增子集的方法不适用（即DP）。
索性该题只需要求出是否存在长度>=3，则可以使用2个int变量min1, min2，代表最小数和第二小的数，只要在遍历过程中出现>=min2的数就可以返回true.
Time Complexity：
O(n)时间
完整代码：
bool increasingTriplet(vector<int>& nums) { if(nums.size() < 3) return false; int min1 = INT_MAX, min2 = INT_MAX; for(int i = 0; i < nums.size(); i++) { if(nums[i] < min1) min1 = nums[i]; if(nums[i] < min2 && nums[i] > min1) min2 = nums[i]; if(nums[i] > min2) return true; } return false; }
