目录
力扣LeetCode-300. 最长递增子序列
Problem Description
给你一个整数数组 n u m s nums nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， [ 3 , 6 , 2 , 7 ] [3,6,2,7] [3,6,2,7] 是数组 [ 0 , 3 , 1 , 6 , 2 , 2 , 7 ] [0,3,1,6,2,2,7] [0,3,1,6,2,2,7] 的子序列。
Tips
- 1 ≤ n u m s . l e n g t h ≤ 2500 1 \leq nums.length \leq 2500 1≤nums.length≤2500
- − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \leq nums[i] \leq 10^4 −104≤nums[i]≤104
Sample I
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
Sample II
输入：nums = [0,1,0,3,2,3]
Sample III
输入：nums = [0,1,0,3,2,3]
输出：4
解题思路
使用一个数组d[]，其中d[i]代表长度为i的最长递增子序列的最后一个元素的最小值。
这么说不容易理解，直接结合实例比较容易理解。
假如输入序列是
[0,8,4,12,2,6]
- 初始d的长度len是0；所以我们直接放入第一个元素0，d就变成了[0]，长度是1；
- 然后看第二个元素8。8>0，所以选8不影响选0。因此8直接放到数组的后面：d变成了[0,8]，长度len是2
- 然后看第3个元素4。4<8，说不定后面有个5>4但是5<8，因此我们要把8换成4，d变成了[0,4]，长度还是2，但是里面的元素更小了，后面就更容易保持递增。
- 看第4个元素12。12>4直接添加到d末尾：d变成[0,4,12]，长度为3。
- 看第5个元素2，2<12且2<4但是2>0。和上面道理相同，d中元素越小越好，把4换成2，d就变成了[0,2,12]。
- 看第6个元素6，6<12,6>2，所以把12换成6，d变成了[0,2,6]，长度为3，即为最终答案。
具体如何实现可以参考一下代码。
AC代码
class Solution
{
public:
int lengthOfLIS(vector<int> &nums)
{
memset(d, 0, sizeof(d));
int len=0; // 长度
d[len++]=nums[0]; // 数组为空的情况下第一个数肯定能直接放进去
for(int i=1;i<nums.size();i++) // 遍历每一个数
{
int thisNum=nums[i]; // 这个数
if(thisNum>d[len-1]) // 如果大于最后一个数，那么就可以直接添加到末尾
{
d[len++]=thisNum;
}
else // 否则
{
int *it=lower_bound(d,d+len,thisNum); // 找到第一个大于等于它的位置
*it=thisNum; // 用这个更小的数来替换之前的比它大的数
}
}
return len; // 返回长度
}
};
原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/119108649