334. 递增的三元子序列
这个题还挺有意思的。
两种解法
方法1：运用题目要求是"三元"的特性
预处理出一个mn：0~i中的最小元素大小
预处理出一个mx：i~n-1中的最大元素大小
判断是否存在mn[i-1] < nums[i] && nums[i] < mx[i+1]就说明存在三元组
复杂度为O(n)
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
vector<int>mn(n),mx(n);
mn[0]=nums[0],mx[n-1]=nums[n-1];
int cur=nums[0];
for(int i=0;i<nums.size();i++){
cur=min(cur,nums[i]);
mn[i]=cur;
}
cur=nums[n-1];
for(int i=n-1;i>=0;i--){
cur=max(cur,nums[i]);
mx[i]=cur;
}
for(int i=1;i<n-1;i++){
if(nums[i]>mn[i-1] && nums[i]<mx[i+1])return true;
}
return false;
}
};
方法2：栈优化的LIS
朴素LIS的复杂度为
栈优化后的LIS复杂度为，因为在栈中使用了二分
这种方法拓展到n元也可以做，但是不符合题目的复杂度为，但是如果是三元组，复杂度应该是
还是符合题意(¬◡¬)✧
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
int len=0;
int stk[n];
for(auto i:nums){
if(len==0 || i>stk[len-1])stk[len++]=i;
else{
int pos=lower_bound(stk,stk+len,i)-stk;
stk[pos]=i;
}
if(len>=3)return true;
}
return false;
}
};
