LeetCode 「中等」300.最长递增子序列
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
输入：nums = [0,1,0,3,2,3]
输出：4
输入：nums = [7,7,7,7,7,7,7]
输出：1
解答
动态规划
动态规划是解决这个问题的直观方法。我们用一个数组 dp 来记录每个位置的最长递增子序列长度
- 定义：
dp[i]表示以nums[i]结尾的最长递增子序列的长度 - 初始值：每个
dp[i]至少为 1，因为每个数字本身可以看作一个长度为 1 的递增子序列 - 状态转移：对于每个
i，我们检查所有j < i的位置：- 如果
nums[j] < nums[i]，说明nums[i]可以接在nums[j]后面形成一个更长的递增子序列 - 因此，
dp[i] = max(dp[i], dp[j] + 1)
- 如果
最后，最长递增子序列的长度就是 dp 数组中的最大值
Code
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
if (!nums.length) return 0;
const dp = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
};
二分查找
- 维护一个数组
tails，其中tails[i]表示长度为i + 1的递增子序列的最小尾部元素 - 遍历数组
nums，对于每个数字num：
- 如果
num大于tails最后一个元素，将其追加到tails末尾 - 否则，用二分查找找到
tails中第一个大于等于num的位置，并用num替换该位置的值
- 最终，
tails的长度即为最长递增子序列的长度
为什么是 “最小尾部元素”？
这个定义的核心目的是为了确保我们能够高效地更新和维护递增子序列的尾部元素，从而找到最长的递增子序列。具体来说：
- 如果
tails[i]是长度为i + 1的递增子序列的最小尾部元素，那么任何比tails[i]大的数字都可以接在长度为i + 1的递增子序列后面，形成一个长度为i + 2的递增子序列 - 通过维护最小尾部元素，我们能够确保在更新
tails时，总是能够找到一个更优的递增子序列
Code
var biSearch = function (nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
};
var lengthOfLIS = function(nums) {
const tails = [];
nums.forEach(num => {
if (!tails.length || num > tails[tails.length - 1]) {
tails.push(num);
} else {
const targetIdx = biSearch(tails, num);
tails[targetIdx] = num;
}
});
return tails.length;
};
总结
- 替换操作是为了保持
tails数组的 “最优性”，即每个位置的尾部元素尽可能小 - 直接添加会导致
tails数组失去 “最优性”，并且后续数字无法接在后面 - 替换操作能够确保
tails数组始终保持递增性，并为后续数字提供更多的机会来延长递增子序列