解题思路
使用动态规划。
-
DP数组用来存储该位置的最长子序列长度。 -
设nums[j] < nums[i], dp[i] = Math.max(dp[i], dp[j] + 1),即上一个比它小的数的最长子序列加1 -
遍历dp数组，找出最大值。
可以看官方的图解，很清晰：最长上升子序列
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
const dp = new Array(nums.length).fill(1)
for (let i = 0; i < nums.length; i++) {
// i与i前面的元素比较
for (let j = 0; j < i; j++) {
// 找比i小的元素，找到一个，就让当前序列的最长子序列长度加1
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
// 找出最大的子序列
let res = 0
for (let i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i])
}
return res
};
复杂度分析
时间复杂度：O(n^2)，空间复杂度O(n)
二分法
模拟发牌，只能把点数小的牌压到点数比它大的牌上，如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。如果当前牌有多个堆可供选择，则选择最左边的堆放置。如下图：
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q）
function lengthOfLIS(nums: number[]): number {
// 每堆的堆顶
const top = []
// 牌堆数初始化为0
let piles = 0
for (let i = 0; i < nums.length; i++) {
// 要处理的扑克牌
let poker = nums[i]
// 左堆和最又堆进行二分搜索，因为堆顶是有序排的，最终找到该牌要插入的堆
let left = 0, right = piles
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (top[mid] > poker) {
right = mid
} else if (top[mid] < poker){
left = mid + 1
} else {
right = mid
}
}
// 没找到合适的牌堆，新建一堆
if (left == piles) piles++
// 把这张牌放到堆顶
top[left] = poker
}
return piles
}
这个解法参考300. Longest Increasing Subsequence(Leetcode每日一题-2020.03.14)
时间复杂度为O(nlogn),一次遍历O(n)*二分搜索O(logn)
本文分享自微信公众号 - JavaScript忍者秘籍（js-obok）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
