跳到主内容

【字节算法题】最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入: nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

二分查找思路

先说下这个解法的时间复杂度为 O(nlogn)。下面举例来说明一下

  1. 首先,给你一排扑克牌,我们像遍历数组那样从左到右一张一张处理这些扑克牌,最终要把这些牌分成若干堆。

    image1.png

  2. 然后我们按照以下规则来处理这些扑克牌:
    a. 只能把点数小的牌压到点数比它大的牌上;
    b. 如果当前牌点数较大没有可以放置的堆,则新建一个堆,把这张牌放进去;
    c. 如果当前牌有多个堆可供选择,则选择最左边的那一堆放置

  3. 以上面的扑克牌的例子来说,最终会被分成这样 5 堆(我们认为纸牌 A 的牌面是最大的,纸牌 2 的牌面是最小的)。

    image2.png

为什么上面规则中的第三条:如果当前牌有多个堆可供选择,则选择最左边的那一堆放置

因为这样可以保证牌堆顶的牌有序

比方说上面这张图,细看下,是不是按照有序的顺序排列的 2, 4, 7, 8, Q

image3.png

  1. 按照上述规则执行,可以算出最长递增子序列,牌的堆数就是最长递增子序列的长度

image4.png

每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗,牌堆顶的牌不是有序吗,这就能用到二分查找了:用二分查找来搜索当前牌应放置的位置。

代码实现

/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
// 每堆的堆顶
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) {
let mid = left + ((right - left) >> 1);
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;
};

动态规划思路

  1. dp[i] 含义:从 0 到下标为 i 的序列的最长子序列长度

    image.png image.png

  2. 根据这个定义,我们的最终结果(子序列的最大长度)应该是 dp 数组中的最大值。

// 找出最大的子序列
let res = 0;
for (let i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
  1. 假设我们已经知道了 dp[0..4] 的所有结果,我们如何通过这些已知结果推出 dp[5] 呢?

    image.png

  2. nums[5] = 3,既然是递增子序列,我们只要找到前面那些结尾比 3 小的子序列,然后把 3 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一。

代码实现

/**
* @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);
}
}
}
// 找出最大的子序列
return Math.max(...dp);
};

附上leetcode 地址