本文共 1037 字，大约阅读时间需要 3 分钟。

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

 

思路：遍历一遍给定数组，维护一个数组dp，dp[i]表示长度为i的LIS的最小结尾，具体操作过程如下：

1、遍历到10，dp[1]=10，长度为1的LIS的最小末尾是10

2、遍历到9，比10小，更新dp[1]=9，长度为1的LIS的最小末尾是9 3、遍历到2，比9小，更新dp[1]=2，长度为1的LIS的最小末尾是2 4、遍历到5，比2大，添加dp[2]=5，长度为2的LIS的最小末尾是5 5、遍历到3，比5小，更新dp[2]=3，长度为2的LIS的最小末尾是3

6、遍历到7，比3大，添加dp[3]=7，长度为3的LIS的最小末尾是7

7、遍历到101，比7大，添加dp[4]=101，长度为4的LIS的最小末尾是101 8、遍历到18，比101小，更新dp[4]=18，长度为4的LIS的最小末尾是18

于是我们知道了LIS的长度为4。

注意，这个2， 3， 7， 18不是LIS，它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。

总结一下：遍历nums，每次采用二分查找法去dp中找最小的比nums[i]大的数：找到了，就用nums[i]进行替换；找不到就将nums[i]添加到dp的末尾，查找过程同，时间复杂度降低到了O(nlogn) 。

class Solution {public:    int lengthOfLIS(vector
   
    & nums) {        vector
    
     dp;        for(auto x:nums){            int l=0, r=dp.size()-1;            while(l<=r){                int mid=(l+r)/2;                if(dp[mid]>=x) r=mid-1;                else l=mid+1;            }            if(l
    
   

 

转载地址：http://mzobi.baihongyu.com/