Just using the LIS to solve the problem in 8ms


  • 3
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            int len=nums.size();
            if(len<=3) return false;
            return LIS(nums)>=3;
        }
        
        int LIS(vector<int> &nums){
            int len=nums.size();
            vector<int> result;
            result.push_back(INT_MIN);
            for(auto num:nums){
                if(result[result.size()-1]<num)   
                    result.push_back(num);
                else {
                    int index=binarySearch(result, num);
                    result[index]=num;
                }
            }
            return result.size()-1;
        }
        
        int binarySearch(vector<int>& nums, int target){
            int start=-1, end=nums.size()-1;
            int mid=0;
            while(end-start>1){
                mid=(start+end)/2;
                if(nums[mid]>=target) end=mid;
                else start=mid;
            }
            return end;
        }
    };

  • 0

    Thanks the post from @alveko

    We do not need to use the binary search to find the position as we only need to update for 3 position.

    So we can optimize the TIME COMPLEXITY to O(N)

    Here is the code:

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            int num1=INT_MAX, num2=INT_MAX;
            for(int x:nums){
                if(x<=num1){
                    num1=x;
                }
                else if(x<=num2){
                    num2=x;
                }
                else{
                    return true;
                }
            }
            return false;
        }
    };

  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.