Increasing Triplet Subsequence
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, ksuch 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 .
Credits:
Special thanks to for adding this problem and creating all test cases.
C++
/*
判断是否存在增序排列的三元子序列（元素不用连续）
用两个临时变量存储第一个数和第二个数，x当做第三个数
例1：
input = [1 4 2 5 3]
c1，c2初始化为最大值INT_MAX
c1 = 1
c2 = 4 -> c2 =2 -> c3 =5 ,return true
例2：
[2 4 1 5]
c1 = 2， c2 = 4， c1 = 1， c3 = 5,return true，
能走到c3说明存在，但是c1，c2, c3存的数并不一定是符合要求的（顺序可能不对）
O(n),O(1)
类似问题：
*/
#include <climits>
class Solution
{
public :
bool increasingTriplet ( vector < int >& a )
{
if ( a . size ()< 3 ) return false ;
int c1 = INT_MAX , c2 = INT_MAX ;
for ( int x : a )
{
if ( x <= c1 ) c1 = x ; //c1为扫描过程中遇到的最小数，是第一个数的候选
else if ( x <= c2 ) c2 = x ; //当x>c1时,x可能为c2或者c3
else return true ; //c1<c2<x，说明这样的三元子序列存在
}
return false ;
}
};
/*错误：没有考虑元素可以不连续
class Solution
{
public:
bool increasingTriplet(vector<int>& a)
{
if(a.size()<3) return false;
for(int i = 0; i<a.size()-2; i++) //从第一个数扫描至倒数第3个元素
{
if(a[i]<a[i+1] && a[i+1] < a[i+2]) return true;
}
return false;
}
};*/