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){
    1. //最长子序列要尽量的长,
    2. auto it=lower_bound(d.begin(),d.end(),val);
    3. if(it!=d.end())
    4. *it=val;
    5. else
    6. d.push_back(val);
    } return d.size(); }

```

复杂度分析

  • 时间复杂度:最长子序列算法 - 图1
  • 空间复杂度:最长子序列算法 - 图2