O(nlgn) 3ms C++ based on GREAKS


  • 0
    H
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
        if(nums.empty())return 0;
        vector<int> tail;
        tail.push_back(nums[0]);
            for(int x: nums){
                if(x<tail[0]) tail[0]=x;
                else if(x>tail.back())tail.push_back(x);
                else{
                    int left = 0, right = tail.size();
                    while(left<right){
                        int mid = left + (right-left)/2;
                        if(tail[mid]>=x) right = mid;
                        else left = mid+1;
                    }
                    tail[left]=x;
                }
            }
            return tail.size();
        }
    };

Log in to reply
 

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