leetcode: 最长上升子序列

题目描述：

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

示例:

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

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路分析：

思路一：根据题目的提示，利用动态规划，可以用O(N^2)的复杂度解这题。直接利用一个dp数组，用从后往前的方式存每个元素当前的最长上升序列，更新的状态转移方程就是dp[i] = max(dp[i], dp[j]+1)，这里j的取值是从i+1到dp.size()。

思路二：由于题目的进阶要求是需要将复杂度降到O(NlogN)，logn顺利成章会想到用二分查找来降低这个复杂度。实际上这部分的思想是维护一个tail数组，遍历nums数组时，每次都在tail数组中去找大于当前值的树，若有则替换，若没有则将当前值加入tail数组。进行替换的原因是在后续的查找中，可以找到更长的子序列，由于当前的tail中的元素更小了。而实际上，只有在添加新元素时会改变最长子序列的大小，因此这个tail数组的长度始终维持在当前最长子序列的长度。这里在查找数用到了二分查找，代码中直接调用了lower_bound()函数。关于这个函数的说明如下：

第一个first参数是一段连续空间的首地址，last是连续空间末端的地址，val是要查找的值。调用lower_bound()的前提是这段连续的空间里的元素是有序（递增）的。
然后lower_bound()的返回值是第一个大于等于val的值的地址，用这个地址减去first，得到的就是第一个大于等于val的值的下标

同时注意区分另一个upper_bound函数，这个返回值是第一个大于val值的地址。

代码：

思路一：

 class Solution {

 public:

     int lengthOfLIS(vector<int>& nums) {

         if(nums.size()==)

             return ;

         vector<int>dp(nums.size(), );

         for(int i=nums.size()-; i>=; i--)

         {

             for(int j=i+; j<nums.size(); j++)

             {

                 if(nums[j] > nums[i])

                 {

                     dp[i] = max(dp[i], dp[j]+);

                 }

             }

         }

         int max = ;

         for(int i=; i<dp.size(); i++)

         {

             if(dp[i]>max)

                 max = dp[i];

         }

         return max;

     }

 };

思路二：

 class Solution {

 public:

     int lengthOfLIS(vector<int>& nums) {

         if(nums.size()==)

             return ;

         vector<int> res;

         for(int i=; i<nums.size(); i++)

         {

             auto iter = lower_bound(res.begin(), res.end(), nums[i]);

             if(iter == res.end())

                 res.push_back(nums[i]);

             else

                 *iter = nums[i];

         }

         return res.size();

     }

 };

巴特西

leetcode: 最长上升子序列

最新文章

热门文章