300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

求取最长子序列，那么对于该最长子序列d，相邻两个数的间隔最小，即保证对该序列的任意长度i,都可以保证如下：

• d[i-1]为当前长度情况下的最小值

  实现

  lower_bound(value):查询数组中第一个>=value的值！ ```cpp int lengthOfLIS(vector& nums) { vector d; for(auto val:nums){

    //最长子序列要尽量的长，
    auto it=lower_bound(d.begin(),d.end(),val);
    if(it!=d.end())
        *it=val;
    else
        d.push_back(val);

  } return d.size(); }

```

复杂度分析

• 时间复杂度:
• 空间复杂度: