[LeetCode] Longest Increasing Subsequence 最长递增子序列

时间:2022-05-29 14:41:04

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

这道题让我们求最长递增子串 Longest Increasing Subsequence 的长度,简称 LIS 的长度。我最早接触到这道题是在 LintCode 上,可参见我之前的博客 Longest Increasing Subsequence,那道题写的解法略微复杂,下面来看其他的一些解法。首先来看一种动态规划 Dynamic Programming 的解法,这种解法的时间复杂度为 O(n2),类似 brute force 的解法,维护一个一维 dp 数组,其中 dp[i] 表示以 nums[i] 为结尾的最长递增子串的长度,对于每一个 nums[i],从第一个数再搜索到i,如果发现某个数小于 nums[i],更新 dp[i],更新方法为 dp[i] = max(dp[i], dp[j] + 1),即比较当前 dp[i] 的值和那个小于 num[i] 的数的 dp 值加1的大小,就这样不断的更新 dp 数组,到最后 dp 数组中最大的值就是我们要返回的 LIS 的长度,参见代码如下:
解法一:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), );
int res = ;
for (int i = ; i < nums.size(); ++i) {
for (int j = ; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + );
}
}
res = max(res, dp[i]);
}
return res;
}
};

下面来看一种优化时间复杂度到 O(nlgn) 的解法,这里用到了二分查找法,所以才能加快运行时间哇。思路是,先建立一个数组 ends,把首元素放进去,然后比较之后的元素,如果遍历到的新元素比 ends 数组中的首元素小的话,替换首元素为此新元素,如果遍历到的新元素比 ends 数组中的末尾元素还大的话,将此新元素添加到 ends 数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比 ends 数组首元素大,比尾元素小时,此时用二分查找法找到第一个不小于此新元素的位置,覆盖掉位置的原来的数字,以此类推直至遍历完整个 nums 数组,此时 ends 数组的长度就是要求的LIS的长度,特别注意的是 ends 数组的值可能不是一个真实的 LIS,比如若输入数组 nums 为 {4, 2, 4, 5, 3, 7},那么算完后的 ends 数组为 {2, 3, 5, 7},可以发现它不是一个原数组的 LIS,只是长度相等而已,千万要注意这点。参见代码如下:

解法二:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return ;
vector<int> ends{nums[]};
for (auto a : nums) {
if (a < ends[]) ends[] = a;
else if (a > ends.back()) ends.push_back(a);
else {
int left = , right = ends.size();
while (left < right) {
int mid = left + (right - left) / ;
if (ends[mid] < a) left = mid + ;
else right = mid;
}
ends[right] = a;
}
}
return ends.size();
}
};

我们来看一种思路更清晰的二分查找法,跟上面那种方法很类似,思路是先建立一个空的 dp 数组,然后开始遍历原数组,对于每一个遍历到的数字,用二分查找法在 dp 数组找第一个不小于它的数字,如果这个数字不存在,那么直接在 dp 数组后面加上遍历到的数字,如果存在,则将这个数字更新为当前遍历到的数字,最后返回 dp 数组的长度即可,注意的是,跟上面的方法一样,特别注意的是 dp 数组的值可能不是一个真实的 LIS。参见代码如下:

解法三:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = ; i < nums.size(); ++i) {
int left = , right = dp.size();
while (left < right) {
int mid = left + (right - left) / ;
if (dp[mid] < nums[i]) left = mid + ;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
};

下面来看两种比较 tricky 的解法,利用到了 C++ 中 STL 的 lower_bound 函数,lower_bound 返回数组中第一个不小于指定值的元素,跟上面的算法类似,还需要一个一维数组v,然后对于遍历到的 nums 中每一个元素,找其 lower_bound,如果没有 lower_bound,说明新元素比一维数组的尾元素还要大,直接添加到数组v中,跟解法二的思路相同了。如果有 lower_bound,说明新元素不是最大的,将其 lower_bound 替换为新元素,这个过程跟算法二的二分查找法的部分实现相同功能,最后也是返回数组v的长度,注意数组v也不一定是真实的 LIS,参见代码如下:

解法四:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
auto it = lower_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}
       return v.size();
}
};

既然能用 lower_bound,那么 upper_bound 就耐不住寂寞了,也要出来解个题。upper_bound 是返回数组中第一个大于指定值的元素,和 lower_bound 的区别时,它不能返回和指定值相等的元素,那么当新进来的数和数组中尾元素一样大时,upper_bound 无法返回这个元素,那么按算法三的处理方法是加到数组中,这样就不是严格的递增子串了,所以要做个处理,在处理每个新进来的元素时,先判断数组v中有无此元素,有的话直接跳过,这样就避免了相同数字的情况,参见代码如下:

解法五:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
if (find(v.begin(), v.end(), a) != v.end()) continue;
auto it = upper_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}
return v.size();
}
};

还有一种稍微复杂点的方法,参见我的另一篇博客 Longest Increasing Subsequence,那是 LintCode 上的题,但是有点不同的是,那道题让求的 LIS 不是严格的递增的,允许相同元素存在。

Github 同步地址:

https://github.com/grandyang/leetcode/issues/300

类似题目:

Increasing Triplet Subsequence

Russian Doll Envelopes

Maximum Length of Pair Chain

Number of Longest Increasing Subsequence

Minimum ASCII Delete Sum for Two Strings

参考资料:

https://leetcode.com/problems/longest-increasing-subsequence/

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74825/Short-Java-solution-using-DP-O(n-log-n)

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74848/9-lines-C%2B%2B-code-with-O(NlogN)-complexity

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74989/C%2B%2B-Typical-DP-N2-solution-and-NLogN-solution-from-GeekForGeek

LeetCode All in One 题目讲解汇总(持续更新中...)