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
題目意思：
判斷一個數(shù)組是否有遞增的長度>=3的子集（順序不變）。
解題方法：
因為需要O(n)的時候解決，所以求最長遞增子集的方法不適用（即DP）衫冻。
索性該題只需要求出是否存在長度>=3，則可以使用2個int變量min1, min2，代表最小數(shù)和第二小的數(shù)唧喉，只要在遍歷過程中出現(xiàn)>=min2的數(shù)就可以返回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; }
