给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入:[10,9,2,5,3,7,101,18]输出:4解释:最长的上升子序列是[2,3,7,10
给定一个无序的整数数组&＃xff0c;找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]&＃xff0c;它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合&＃xff0c;你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路&＃xff1a;
这道题参考了博文的思路
https://www.cnblogs.com/grandyang/p/4938187.html
时间复杂度O(nlogn)&＃xff0c;自己没想出来&＃xff0c;而且感觉太复杂。具体思路如下&＃xff1a;
维护一个递增数组dp&＃xff0c;如果当前元素比dp的第一个元素小&＃xff0c;就把第一个元素替换掉&＃xff08;覆盖第一个元素&＃xff09;&＃xff0c;如果比最后一个元素大&＃xff0c;就插入到dp的最后&＃xff08;不覆盖最后一个元素&＃xff09;&＃xff0c;如果大小位于第一个元素和最后一个元素中&＃xff0c;就通过二分法找到第一个大于该元素的位置&＃xff0c;替换掉原始元素&＃xff08;覆盖&＃xff09;。
代码如下&＃xff1a;
int lengthOfLIS(vector& nums) {vector dp;if (nums.size() <&＃61; 0) {return 0;}dp.push_back(nums[0]);for (int i &＃61; 1; i dp[dp.size() - 1]) {dp.push_back(nums[i]);continue;}int left &＃61; 0;int right &＃61; dp.size()-1;while (left 思路2&＃xff1a;采用dp来做&＃xff0c;通过维护一个一维数组dp来做&＃xff0c;dp[i]表示到第i个元素的最长子序列的个数&＃xff0c;那么dp[i&＃43;1]的值等于遍历[0,j]的元素&＃xff08;0<&＃61;j<&＃61;i&＃xff09;&＃xff0c;如果对应的nums[j] dp[i] &＃61; max(dp[j] &＃43; 1, dp[i]);
如果遍历完j都没有元素满足nums[j] 参考代码&＃xff1a;
int lengthOfLIS(vector& nums) {if(nums.size()&＃61;&＃61;0){return 0;}int *dp &＃61; new int[nums.size()];int res &＃61; 1;for (int i &＃61; 1; i 思路三&＃xff1a;这道题还可以用二分查找&＃43;动态规划来做&＃xff0c;声明一个一维的数组&＃xff08;初始化为空&＃xff09;res&＃xff0c;其中res表示截止到下标i时&＃xff0c;当前存的可能的最长递增子序列&＃xff0c;注意这时res中不一定是递增的子序列&＃xff0c;但是res的size就是当前最优的递增子序列的长度。
示例如下&＃xff1a;
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
A[0] &＃61; 0. Case 1. There are no active lists, create one.
0.
-----------------------------------------------------------------------------
A[1] &＃61; 8. Case 2. Clone and extend.
0.
0, 8.
-----------------------------------------------------------------------------
A[2] &＃61; 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
-----------------------------------------------------------------------------
A[3] &＃61; 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
-----------------------------------------------------------------------------
A[4] &＃61; 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
-----------------------------------------------------------------------------
A[5] &＃61; 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
-----------------------------------------------------------------------------
A[6] &＃61; 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
-----------------------------------------------------------------------------
A[7] &＃61; 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[8] &＃61; 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[9] &＃61; 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
-----------------------------------------------------------------------------
A[10] &＃61; 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
-----------------------------------------------------------------------------
A[11] &＃61; 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[12] &＃61; 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[13] &＃61; 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
-----------------------------------------------------------------------------
A[14] &＃61; 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------------------------
A[15] &＃61; 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------------------------
如图所示&＃xff0c;每次我们都会维护多个队列&＃xff0c;这样每个队列就是有序的&＃xff0c;但是其实没必要这么复杂&＃xff0c;我们只需要维护一个队列res即可。只需要遍历一遍原数组nums&＃xff0c;每次取出当前值n&＃61;nums[i]&＃xff0c;判断在res中第一个大于等于n的下标&＃xff0c;覆盖下标对应的元素&＃xff0c;如果没找到&＃xff0c;证明比所有res的元素都大&＃xff0c;那么在res的尾部加上n元素&＃xff0c;最后返回res.size()即可。
参考代码&＃xff08;时间复杂度nlogn&＃xff09;&＃xff1a;
class Solution {
public:
int lengthOfLIS(vector& nums) {vector res;for (int &n : nums) {auto it &＃61; lower_bound(res.begin(), res.end(), n);if (it &＃61;&＃61; res.end()) res.push_back(n);else *it &＃61; n;}return res.size();
}
};
京公网安备 11010802041100号