LeetCode 300. 最长递增子序列：两种解法从入门到优化

LeetCode 经典中等难度题目——300. 最长递增子序列Longest Increasing Subsequence简称LIS是动态规划入门阶段的核心必刷题。该题目存在两种主流解法一种为基础动态规划解法另一种为结合二分查找的优化解法后者可将时间复杂度大幅降低是面试与笔试中的高频考点具有重要的学习价值。本文首先明确题目核心要求给定一个整数数组 nums求解其中最长严格递增子序列的长度。题目对「子序列」的定义为由数组派生而来的序列可通过删除或不删除数组中的元素且不改变其余元素的相对顺序得到。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列其核心特征为「不改变元素相对顺序、元素可不连续」。举例说明对于数组 nums [10,9,2,5,3,7,101,18]其最长严格递增子序列为 [2,3,7,101] 或 [2,5,7,101]两种子序列的长度均为 4因此该数组的最长严格递增子序列长度为 4。下文将从基础解法到优化解法逐步拆解结合提供的代码及详细思路进行分析确保逻辑清晰、易于理解。解法一动态规划DP—— 入门核心解法思路核心动态规划的核心在于「定义状态」与「推导状态转移方程」针对本题结合代码细节逐一拆解如下定义状态设 dp[i] 表示「以 nums[i] 为结尾」的最长严格递增子序列的长度。状态转移对于每个索引 i取值范围为 0 至 n-1遍历其之前的所有索引 j取值范围为 0 至 i-1。若 nums[j] nums[i]则说明 nums[i] 可接在 nums[j] 之后构成更长的严格递增子序列此时需更新当前最长子序列长度若不存在满足条件的 j则 nums[i] 自身构成一个长度为 1 的严格递增子序列即 dp[i] 的初始值。最终答案dp 数组中的最大值即为整个数组的最长严格递增子序列长度。代码实现TypeScript以下为基础解法的代码实现附带详细注释便于理解各步骤的核心作用functionlengthOfLIS_1(nums:number[]):number{constNnums.length;if(N0)return0;// 边界处理空数组直接返回0避免后续代码报错constdpnewArray(N).fill(1);// 初始化dp数组每个元素默认值为1自身构成子序列for(leti0;iN;i){letres1;// 临时存储以nums[i]为结尾的最长子序列长度初始值为1for(letj0;ji;j){// 遍历所有前序元素若满足递增条件则更新最长子序列长度if(nums[j]nums[i]){resMath.max(dp[j]1,res);}}dp[i]res;// 确定以nums[i]为结尾的最长严格递增子序列长度}returnMath.max(...dp);// 返回dp数组最大值即目标结果};复杂度分析时间复杂度O(n²)。算法包含两层嵌套循环外层循环遍历数组的 n 个元素内层循环对于每个元素最多遍历 i 次i 从 0 至 n-1整体时间复杂度近似为 n²。空间复杂度O(n)。仅使用一个长度为 n 的 dp 数组存储状态空间开销与数组长度线性相关。小总结该解法逻辑直观是动态规划入门阶段的典型案例核心在于理解「以当前元素为结尾」的状态定义此类思路同样适用于最长公共子序列等同类动态规划题目。但该解法存在明显局限性当数组长度 n 较大时如 n10⁴O(n²) 的时间复杂度会超出题目时间限制因此需进一步优化解法以提升效率。解法二动态规划 二分查找——优化至 O(nlogn) 复杂度思路核心该解法是对基础动态规划解法的核心优化核心思路为「维护一个单调递增的辅助数组 dp」。需特别注意此处的 dp 数组与基础解法中的 dp 数组功能完全不同其作用为存储「长度为 k 的最长严格递增子序列的最小末尾元素」。结合代码实现将该思路拆解为以下步骤便于理解初始化一个空的辅助数组 dp用于存储「长度为 k 的最长严格递增子序列的最小末尾元素」。遍历数组 nums 中的每个元素 num若 num 大于 dp 数组的最后一个元素说明 num 可接在 dp 数组末尾构成更长的严格递增子序列直接将 num 加入 dp 数组。若 num 小于或等于 dp 数组的最后一个元素说明 num 无法直接接在 dp 数组末尾但可替换 dp 数组中的某个元素使 dp 数组保持单调递增且尽可能使末尾元素更小便于后续加入新元素以构成更长子序列。此时通过二分查找找到 dp 数组中第一个大于或等于 num 的元素位置将该位置的元素替换为 num。最终辅助数组 dp 的长度即为原数组的最长严格递增子序列长度。举个例子理解以数组 nums [10,9,2,5,3,7,101,18] 为例结合上述思路逐步分析辅助数组 dp 的变化过程遍历元素 10dp 数组为空直接将 10 加入 dp → dp [10]遍历元素 99 ≤ 10通过二分查找找到 dp 数组中第一个大于或等于 9 的位置索引 0将该位置元素替换为 9 → dp [9]遍历元素 22 ≤ 9通过二分查找找到 dp 数组中第一个大于或等于 2 的位置索引 0将该位置元素替换为 2 → dp [2]遍历元素 55 2将 5 加入 dp 数组 → dp [2,5]遍历元素 33 ≤ 5通过二分查找找到 dp 数组中第一个大于或等于 3 的位置索引 1将该位置元素替换为 3 → dp [2,3]遍历元素 77 3将 7 加入 dp 数组 → dp [2,3,7]遍历元素 101101 7将 101 加入 dp 数组 → dp [2,3,7,101]遍历元素 1818 ≤ 101通过二分查找找到 dp 数组中第一个大于或等于 18 的位置索引 3将该位置元素替换为 18 → dp [2,3,7,18]最终 dp 数组的长度为 4与预期结果一致。需重点说明辅助数组 dp 本身并非最长严格递增子序列其长度仅与最长严格递增子序列的长度相等这是该优化解法的核心易错点。代码实现TypeScript以下为优化解法的代码实现附带详细注释拆解二分查找的核心逻辑functionlengthOfLIS_2(nums:number[]):number{constNnums.length;if(N0)return0;// 边界处理空数组直接返回0constdp:number[][];// 辅助数组存储长度为k的最长严格递增子序列的最小末尾元素for(constnumofnums){// 情况1num大于dp数组最后一个元素直接加入构成更长子序列if(dp.length0||numdp[dp.length-1]){dp.push(num);}else{// 情况2通过二分查找找到第一个≥num的位置并替换保证dp数组单调递增且末尾元素最小let[l,r][0,dp.length-1];letres0;// 存储替换索引初始值设为0作为兜底while(lr){constmid(lr)1;// 等价于Math.floor((lr)/2)位运算效率更高if(numdp[mid]){rmid-1;// 向左缩小查找范围寻找更靠前的≥num的元素resmid;// 更新替换索引}else{lmid1;// 向右缩小查找范围当前mid位置元素小于num不满足替换条件}}dp[res]num;// 替换对应位置元素维持dp数组的单调递增特性}}returndp.length;// dp数组的长度即为最长严格递增子序列的长度};复杂度分析时间复杂度O(nlogn)。遍历数组的时间复杂度为 O(n)每次遍历中执行二分查找的时间复杂度为 O(logk)其中 k 为当前 dp 数组的长度最大为 n因此整体时间复杂度为 O(nlogn)。空间复杂度O(n)。辅助数组 dp 的最大长度为 n即当原数组本身为严格递增数组时dp 数组长度与原数组长度一致。小总结该解法的核心在于理解辅助数组的含义——其并非存储最长严格递增子序列本身而是存储「长度为 k 的最长严格递增子序列的最小末尾元素」。通过贪心策略使末尾元素尽可能小便于后续加入新元素与二分查找快速定位替换位置的结合将时间复杂度从 O(n²) 优化至 O(nlogn)适用于处理大规模数组。在面试中能够写出该优化解法可充分体现对算法思路的深入理解与优化能力。两种解法对比及适用场景解法时间复杂度空间复杂度适用场景动态规划解法一O(n²)O(n)数组长度较小n ≤ 1000、入门阶段理解动态规划思路DP 二分查找解法二O(nlogn)O(n)数组长度较大n 1000、面试优化要求、追求高效算法刷题技巧及易错点提醒1. 边界处理不可遗漏当输入数组为空时需直接返回 0该细节易被忽略可能导致测试用例执行失败对应代码中 if (N 0) return 0; 语句。2. 二分查找细节需注意循环条件需设为 l ≤ r替换索引 res 的初始值及更新时机需准确把控避免出现定位错误例如当 num 小于 dp 数组中所有元素时res 保持初始值 0替换 dp 数组第一个元素。3. 两种解法的本质区别基础动态规划解法关注「以每个元素为结尾的最长严格递增子序列」可明确获取具体子序列优化解法关注「最小末尾元素」仅能得到子序列长度无法直接获取具体子序列但效率更优。4. 代码优化细节优化解法中使用的位运算 (l r) 1等价于 Math.floor((l r)/2)但运行效率更高在面试中合理使用此类优化可体现代码编写的专业性。本题的两种解法基本覆盖了最长递增子序列的核心考点建议先掌握基础动态规划解法理解动态规划的核心思路再逐步学习优化解法体会贪心策略与二分查找的结合技巧。对于最长非递减子序列、最长递增子数组等同类变形题目可借鉴本文思路进行求解。