mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
118 lines
4.0 KiB
Markdown
118 lines
4.0 KiB
Markdown
# [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
|
||
# 思路
|
||
给定一个数组，求最长递增子序列的长度。
|
||
|
||
## 思路一、O(n^2)
|
||
很明显是一个动态规划题，我们可以用dp[i]表示以nums[i]为结尾的最长子序列的长度。这样更新dp[i]的转移方程就为
|
||
```
|
||
for all j in [0, i-1]:
|
||
if nums[i] >= nums[j]:
|
||
dp[i] = max(dp[i], dp[j] + 1)
|
||
```
|
||
从转移方程可以看出有两层循环，所以时间复杂度为O(n^2)。
|
||
|
||
## 思路二、O(nlogn)
|
||
思路一比较好想，O(nlogn)的就不太好想了，可参考[这里](https://segmentfault.com/a/1190000003819886)，讲得比较清楚。
|
||
|
||
核心思路就是：
|
||
> 维护一个长度可变的数组tails, tails[i]表示长度为i+1的所有递增子序列中最小的那个末尾元素，这样更新完毕后tails的长度即结果。
|
||
|
||
下面举个[例子](https://segmentfault.com/a/1190000003819886)说明:
|
||
在`1,3,5,2,8,4,6`这个例子中，当到6时，我们一共可以有四种长度的递增子序列，在每种子序列中我们取末尾元素最小的，那么这四个序列分别是
|
||
```
|
||
1
|
||
1,2
|
||
1,3,4
|
||
1,3,5,6
|
||
```
|
||
为什么要选末尾元素最小的呢，是因为在长度一定的情况下，末尾元素最小的是未来最有可能成为最长序列的候选人。这样，每来一个新的数，
|
||
我们便按照以下规则更新这些序列：
|
||
1. 如果nums[i]比所有序列的末尾都大，说明有更长的递增序列产生，我们把最长的序列复制一遍，并加上这个nums[i]。
|
||
2. 否则，我们从前往后找，找到第一个末尾大于等于自己的那个序列，更新这个末尾。
|
||
|
||
比如这时，如果再来一个9，那就是第1种情况，更新序列为
|
||
```
|
||
1
|
||
1,2
|
||
1,3,4
|
||
1,3,5,6
|
||
1,3,5,6,9
|
||
```
|
||
|
||
如果再来一个3，那就是第2种情况，更新序列为
|
||
```
|
||
1
|
||
1,2
|
||
1,3,3
|
||
1,3,5,6
|
||
```
|
||
如果再来一个0，还是第2种情况，更新序列为
|
||
```
|
||
0
|
||
1,2
|
||
1,3,3
|
||
1,3,5,6
|
||
```
|
||
|
||
我们用一个长度可变的tails数组存储上述所有序列的末尾值（因为我们只用到了末尾值），因此tails是个递增数组，这样在第2种情况进行查找的时候就可以使用二分查找了，使复杂度降为O(nlogn)。
|
||
|
||
注意二分查找有现成的库函数：
|
||
* lower_bound(first, last, val): 返回有序数组或容器的[first, last)范围内**第一个大于或等于**val的元素的位置(指针或者迭代器,下同);
|
||
* upper_bound(first, last, val): 返回有序数组或容器的[first, last)范围内**第一个大于**val的元素的位置;
|
||
|
||
可见这里我们应该使用`lower_bound`找到第一个大于等于target的位置。
|
||
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int lengthOfLIS(vector<int>& nums) {
|
||
int n = nums.size();
|
||
if(n <= 1) return n;
|
||
vector<int>dp(n, 1);
|
||
|
||
int res = 1;
|
||
for(int i = 1; i < n; i++){
|
||
// j >= 0 可优化成 j >= dp[i]-1
|
||
for(int j = i-1; j >= 0; j--)
|
||
if(nums[i] > nums[j])
|
||
dp[i] = max(dp[i], dp[j] + 1);
|
||
|
||
res = max(res, dp[i]);
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int lengthOfLIS(vector<int>& nums) {
|
||
int n = nums.size();
|
||
if(n <= 1) return n;
|
||
|
||
vector<int>tails;
|
||
tails.push_back(nums[0]);
|
||
for(int i = 1; i < n; i++){
|
||
if(nums[i] > tails.back()) tails.push_back(nums[i]);
|
||
else{
|
||
tails[lower_bound(tails.begin(), tails.end(), nums[i]) - tails.begin()] = nums[i];
|
||
// 上面这句等价于下面注释部分
|
||
// int low = 0, high = tails.size() - 1;
|
||
// while(low < high){
|
||
// int mid = low + (high - low) / 2;
|
||
// if(tails[mid] < nums[i]) low = mid + 1;
|
||
// else high = mid;
|
||
// }
|
||
// tails[low] = nums[i];
|
||
}
|
||
}
|
||
return tails.size();
|
||
}
|
||
};
|
||
```
|