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){
} return d.size(); }//最长子序列要尽量的长,
auto it=lower_bound(d.begin(),d.end(),val);
if(it!=d.end())
*it=val;
else
d.push_back(val);
复杂度分析
- 时间复杂度:
- 空间复杂度: