Share my O(nlogn) solution


  • 0
    O
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            if (nums.size() == 0)
                return 0;
            vector<int> indices = {nums[0]};
            for (int i = 1; i < nums.size(); i++) {
                if (indices.back() < nums[i])
                    indices.push_back(nums[i]);
                else {
                    auto iter = lower_bound(indices.begin(), indices.end(), nums[i]);
                    *iter = nums[i];
                }
            }
            return indices.size();
        }
    };

Log in to reply
 

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