LeetCode 300. Longest Increasing Subsequence

发布于: 2020 年 06 月 21 日
LeetCode 300. Longest Increasing Subsequence

问题描述

给定一个未排序的整数数组,找出最长的递增子序列。

栗子:

输入:[10,9,2,5,3,7,101,18]
输出:4
解释:
最长的递增子序列为:[2,3,7,101],长度为 4.

注意:

  • 可能存在多种最长递增子序列的组合,只需要返回其长度即可。

  • 算法时间复杂度需要在 O(n2) 之内。

想看英文原文的戳这里

解题思路

从上面的栗子,我们可以看出,递增子序列不要求连续。

开门见山,直接说下这道题的解法,即动态规划。使用动态规划的思想,在已有结果基础上,计算当前结果。

拿上述栗子举例,[10,9,2,5,3,7,101,18],我们从后往前逐个分析。

为什么要从后往前呢?因为对于我来说这样看起来更直观。当然从前往后也是可行的,当你理解了思想后,可以尝试着从前往后再推导一遍。只不过有些许差别。

从后往前,记录的是以这个数开始的递增子序列的长度。

从前往后,记录的是以这个数结束的递增子序列的长度。

弄清楚上述差别后,再加上下面的逐步推导说明,相信你也能弄明白如何从前往后分析。

下面我们对数字逐个进行分析。将 f(n) 记为从数字 n 开始的最大递增子序列长度。

  • 18。从它开始的递增子序列只有它本身,那么 f(18) = 1

  • 101。其后没有比它大的数字,那么从它开始的递增子序列也只有它自己,f(101) = 1

  • 710118 都比它大,那它跟谁组合在一起更长呢?很简单,只需取 f(101)f(18) 中的最大值,再加上它自身的长度 1,即 f(7) = max(f(101), f(18)) + 1 = 2

  • 37、101、18 比它大,同理,取三者中的最大值,再加上它本身,即 f(3) = max(f(7), f(101), f(18)) + 1 = 3

  • 57、101、18 比它大,同样需要取三者最大值,f(5) = max(f(7), f(101), f(18)) + 1 = 3

  • 25、3、7、101、18 比它大,同样取这几个中的最大值,f(2) = max(f(5), f(3), f(7), f(101), f(18)) + 1 = 4

  • 9101、18 比它大,f(9) = max(f(101), f(18)) + 1 = 2

  • 10101、18 比它大,f(10) = max(f(101), f(18)) + 1 = 2

不知从上面的推导过程中,你有没有发现一些规律?

当计算某个数字的最长递增子序列长度时,根据所有比其大的数字的结果,取出最大值,然后再加上它本身长度 1,即可得出结果。当然,也可能存在根本没有比它大的数字,那么结果就是 1

所以,解题思路总结如下:

  • 对于某个数来说,如果其后没有比其大的数,那么长度为 1

  • 如果有比它大的数,那么取所有大于它的数的结果最大值,再加 1。用数学公式表示如下:

// x/y/z 都大于 n
f(n) = max(f(x), f(y), f(z), ...) + 1

在上述过程中,我们可以计算出以每个数字开始的最长递增子序列长度,那么整体的最长递增子序列长度也自然很好求出。

下面给出 js 代码实现,可以对照着看一下。

var lengthOfLIS = function (nums) {
if (nums && nums.length > 0) {
let result = 1;
// 保存已计算的长度
let lenList = [];
// 从后往前计算
let i = nums.length - 1;
while (i >= 0) {
// 同样从后往前计算比其大的最长递增序列长度
let j = nums.length - 1;
let maxLen = 0;
while (j > i) {
if (nums[j] > nums[i]) {
// 计算 index,最末尾是 0
const index = nums.length - 1 - j;
// 计算最大值
if (index >= 0 && index < lenList.length) {
maxLen = Math.max(maxLen, lenList[index]);
}
}
j -= 1;
}
maxLen += 1;
// 整体最大值
if (result < maxLen) {
result = maxLen;
}
lenList.push(maxLen);
i -= 1;
}
return result;
}
return 0;
};

发布于: 2020 年 06 月 21 日 阅读数: 3
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 300. Longest Increasing Subsequence