A c++ solution using the lower_bound function(8ms).


  • 0
    8
    #include<algorithm>
    class Solution {
    public:
    bool increasingTriplet(vector<int>& nums) {
        if(nums.size()<3) return false;
        vector<int>inc;
        for(int i=0;i<nums.size();i++)
        {
            if(inc.size()>=3) return true;//important
            int ind=lower_bound(inc.begin(),inc.end(),nums[i])-inc.begin();
            if(ind==inc.size())inc.push_back(nums[i]);
            else inc[ind]=nums[i];
        }
        return inc.size()>=3;
    }
    };
    

    If without the condition that the size of the increasing sequence is 3, the complexity of this algorithm is O(nlogn). But since that the size is a constant number, and also the size of the vector 'inc' is a constant number, the time complexity is O(n) and the space is O(1).


Log in to reply
 

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