4ms C++ solution using BS


  • 0
    C

    ...
    class Solution {
    public:
    int findInsertIndex(vector<int>& nums, int key){
    int begin = 0, end = nums.size();
    while (begin < end){
    int mid = begin + (end-begin) / 2;
    if (nums[mid] < key)
    begin = mid + 1;
    else
    end = mid;
    }
    return end;
    }
    int lengthOfLIS(vector<int>& nums) {
    vector<int> LastNums;
    for (auto num : nums)
    {
    int insertIndex = findInsertIndex(LastNums, num);
    if (insertIndex == LastNums.size())
    LastNums.push_back(num);
    else
    LastNums[insertIndex] = num;
    }
    return LastNums.size();

    }
    

    };
    ...


Log in to reply
 

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