334. 递增的三元子序列

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;
    }
};