难度：中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。1
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。2
示例 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
提示：10
-
1 <= nums.length <= 2500 -
-10^4 <= nums[i] <= 10^4
进阶：
你能将算法的时间复杂度降低到 O(nlogn) 吗?
解答
解决这个问题有两种主流方法：一种是基础的动态规划，另一种是更高效的、结合了贪心和二分查找的优化方法。这里将提供完整的两种解法。
最优解是第二种方法，它满足了题目进阶部分的要求。
解法一：贪心 + 二分查找 (最优解)
这种方法是本题的进阶解法，时间复杂度为 O(nlogn)。
核心思想：
我们维护一个 tails 数组，tails[i] 存储的是所有长度为 i+1 的递增子序列中，结尾数字最小的那个值。这个 tails 数组一定是单调递增的。
我们遍历原始数组 nums 中的每个数字 num：
-
如果
num比tails数组的所有元素都大，就意味着num可以接在当前最长的子序列之后，形成一个更长的子序列。我们直接将其追加到tails数组的末尾。 -
否则，在
tails数组中，用二分查找找到第一个大于或等于num的元素，并用num替换它。这一步是关键，它并不会增加子序列的长度，但它用一个更小的数更新了某个长度的子序列的最小末尾值，这为后续元素提供了更大的增长潜力。
最终，tails 数组的长度就是最长递增子序列的长度。
JavaScript 代码实现：
JavaScript
/**
* 进阶解法：贪心 + 二分查找
* @param {number[]} nums 整数数组
* @return {number} 最长严格递增子序列的长度
*
* 时间复杂度: O(n log n)。遍历 nums 为 O(n)，每次遍历中的二分查找为 O(log n)。
* 空间复杂度: O(n)。tails 数组在最坏情况下可能存储 n 个元素。
*/
const lengthOfLIS = function(nums) {
// tails 数组。tails[i] 表示长度为 i+1 的所有递增子序列中，结尾最小的那个元素。
// 这个数组是整个算法的核心，它一定是单调递增的。
const tails = [];
// 遍历输入数组的每一个数字
for (const num of nums) {
// 如果 tails 为空，或者当前数字 num 大于 tails 数组的最后一个元素
// 这意味着 num 可以扩展当前最长的递增子序列，使其变得更长。
if (tails.length === 0 || num > tails[tails.length - 1]) {
// 直接将 num 添加到 tails 数组末尾，最长递增子序列的长度+1
tails.push(num);
} else {
// 如果 num 不大于 tails 的最后一个元素，我们需要在 tails 中找到一个位置来放置 num。
// 目标：找到 tails 中第一个大于或等于 num 的元素，并用 num 替换它。
// 这样做可以优化未来的可能性：在保持子序列长度不变的情况下，让它的结尾数字变得更小。
// 因为 tails 是有序的，我们可以用二分查找来加速这个过程。
let left = 0;
let right = tails.length - 1;
// 二分查找的目的是找到插入或替换的位置
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
// 如果中间值小于 num，说明目标位置在右半部分
left = mid + 1;
} else {
// 如果中间值大于或等于 num，说明目标位置可能就是 mid，或者在左半部分
right = mid;
}
}
// 循环结束后，left (或 right) 就是第一个大于或等于 num 的元素的位置
tails[left] = num;
}
}
// 遍历结束后，tails 数组的长度就是最长递增子序列的长度。
// 注意：tails 数组本身不一定是一个真实的最长递增子序列，但它的长度是正确的。
// 例如，对于 [10,9,2,5,3,7,101,18]，tails 的变化过程是：
// [10] -> [9] -> [2] -> [2, 5] -> [2, 3] -> [2, 3, 7] -> [2, 3, 7, 101] -> [2, 3, 7, 18]
// 最终 tails 为 [2, 3, 7, 18]，其长度 4 就是最终答案。
return tails.length;
};
解法二：动态规划 (基础解法)
这是一种更直观的解法，时间复杂度为 O(n2)。
核心思想：
我们定义一个 dp 数组，其中 dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
为了计算 dp[i]，我们需要回头看 i 之前的所有元素 nums[j] (其中 j < i)。如果 nums[i] > nums[j]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，形成一个更长的递增子序列，长度为 dp[j] + 1。我们遍历所有 j < i 的情况并取最大值。
最后，整个 dp 数组中的最大值就是最终答案。
JavaScript 代码实现：
JavaScript
/**
* 解法二：动态规划
* @param {number[]} nums 整数数组
* @return {number} 最长严格递增子序列的长度
*
* 时间复杂度: O(n^2)，其中 n 是数组 nums 的长度。我们使用了两层嵌套循环。
* 空间复杂度: O(n)，需要一个大小为 n 的 dp 数组。
*/
const lengthOfLIS_DP = function(nums) {
// 边界情况：如果数组为空，则最长递增子序列长度为 0
if (nums.length === 0) {
return 0;
}
// dp 数组定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
// 初始化 dp 数组，每个元素至少可以自成一个子序列，所以初始长度都为 1。
const dp = new Array(nums.length).fill(1);
// 从第二个元素开始遍历数组
for (let i = 1; i < nums.length; i++) {
// 对于当前元素 nums[i]，我们需要向前查找所有比它小的元素
for (let j = 0; j < i; j++) {
// 如果找到了一个前面的、比当前元素小的 nums[j]
if (nums[i] > nums[j]) {
// 说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面，
// 我们需要更新 dp[i] 为 "dp[j] + 1" 和 "当前 dp[i] 值" 中的较大者。
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 遍历完所有元素后，dp 数组中存储了以每个元素结尾的最长子序列长度。
// 我们需要找到这个 dp 数组中的最大值，即为全局的最长递增子序列的长度。
return Math.max(...dp);
};
运行测试用例
JavaScript
console.log("--- 使用最优解 (贪心 + 二分查找) ---");
console.log(`[10,9,2,5,3,7,101,18] 的最长递增子序列长度: ${lengthOfLIS([10,9,2,5,3,7,101,18])}`); // 输出: 4
console.log(`[0,1,0,3,2,3] 的最长递增子序列长度: ${lengthOfLIS([0,1,0,3,2,3])}`); // 输出: 4
console.log(`[7,7,7,7,7,7,7] 的最长递增子序列长度: ${lengthOfLIS([7,7,7,7,7,7,7])}`); // 输出: 1
console.log("\n--- 使用动态规划解法 ---");
console.log(`[10,9,2,5,3,7,101,18] 的最长递增子序列长度: ${lengthOfLIS_DP([10,9,2,5,3,7,101,18])}`); // 输出: 4
console.log(`[0,1,0,3,2,3] 的最长递增子序列长度: ${lengthOfLIS_DP([0,1,0,3,2,3])}`); // 输出: 4
console.log(`[7,7,7,7,7,7,7] 的最长递增子序列长度: ${lengthOfLIS_DP([7,7,7,7,7,7,7])}`); // 输出: 1