题目描述给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例 1text输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4。示例 2text输入nums [0,1,0,3,2,3] 输出4 解释最长递增子序列是 [0,1,2,3] 或 [0,1,3,?] 等长度为 4。示例 3text输入nums [7,7,7,7,7,7,7] 输出1 解释严格递增相同元素不算递增所以最长长度为 1。示例 4text输入nums [1,3,6,7,9,4,10,5,6] 输出6约束条件1 nums.length 2500-10^4 nums[i] 10^4解题思路核心思想这是经典的最长递增子序列LIS问题有两种主流解法动态规划O(n²) 时间O(n) 空间贪心 二分查找O(n log n) 时间O(n) 空间方法一动态规划基础解法思路定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。状态转移方程textdp[i] max(dp[j]) 1, 其中 0 ≤ j i 且 nums[j] nums[i]如果前面没有比nums[i]小的数则dp[i] 1最终答案max(dp[0], dp[1], ..., dp[n-1])代码实现javapublic int lengthOfLIS(int[] nums) { int n nums.length; if (n 0) return 0; int[] dp new int[n]; int maxLength 1; // 初始化每个元素至少可以自己构成一个长度为1的子序列 Arrays.fill(dp, 1); for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } maxLength Math.max(maxLength, dp[i]); } return maxLength; }手动模拟以nums [10, 9, 2, 5, 3, 7, 101, 18]为例inums[i]比较前面所有 jdp[i]计算过程010无1初始值19109 ❌1没有比9小的22102❌, 92❌1没有比2小的3525✅ → dp[2]122前面只有2比5小4323✅ → dp[2]122前面只有2比3小5727✅→2, 57✅→3, 37✅→33max(2,3,3)36101前面所有都小于101取最大dp14max(1,1,1,2,2,3)14718前面小于18的有多个最大dp[6]4等等10118不能用4需要仔细计算...详细计算 i7nums[7]18j0: 1018? 是 → dp[0]12j1: 918? 是 → dp[1]12j2: 218? 是 → dp[2]12j3: 518? 是 → dp[3]13j4: 318? 是 → dp[4]13j5: 718? 是 → dp[5]14j6: 10118? 否 → 跳过max 4所以 dp[7] 4最终 dp 数组[1, 1, 1, 2, 2, 3, 4, 4]最大长度 4✅复杂度分析时间复杂度O(n²) — 双重循环空间复杂度O(n) — dp 数组优缺点✅ 思路直观容易理解✅ 可以记录具体的子序列稍作修改❌ 时间复杂度较高n2500 时勉强可过方法二贪心 二分查找最优解⭐核心思想维护一个数组tails其中tails[i]表示长度为 i1 的递增子序列的末尾元素的最小值。贪心策略为了让子序列尽可能长我们要让末尾元素尽可能小这样更有利于后面接上更大的数。算法步骤遍历每个数num在tails中找到第一个 ≥num的位置二分查找如果找到替换该位置的值为num因为更小的末尾更优如果没找到num大于所有tails中的数则追加到末尾最终tails的长度就是 LIS 的长度为什么贪心成立tails数组是严格递增的对于相同的长度我们保留更小的末尾值这样后面的数更容易接上替换操作不会影响最终长度但可能改变子序列的内容代码实现javapublic int lengthOfLIS(int[] nums) { int n nums.length; if (n 0) return 0; int[] tails new int[n]; int size 0; // 当前 tails 的有效长度 for (int num : nums) { // 二分查找第一个 num 的位置 int left 0, right size; while (left right) { int mid left (right - left) / 2; if (tails[mid] num) { left mid 1; } else { right mid; } } // left 是要替换的位置 tails[left] num; // 如果 left size说明 num 大于所有已有值长度增加 if (left size) { size; } } return size; }使用库函数的简化版javapublic int lengthOfLIS(int[] nums) { int[] tails new int[nums.length]; int size 0; for (int num : nums) { int pos Arrays.binarySearch(tails, 0, size, num); if (pos 0) { pos -pos - 1; // 获取插入点 } tails[pos] num; if (pos size) { size; } } return size; }手动模拟关键nums [10, 9, 2, 5, 3, 7, 101, 18]步骤numtails 数组size操作说明110[10]1初始直接加入29[9]19 10替换 tails[0]932[2]12 9替换 tails[0]245[2, 5]25 2追加到末尾53[2, 3]23 在 2 和 5 之间替换 tails[1]367[2, 3, 7]37 3追加到末尾7101[2, 3, 7, 101]4101 7追加到末尾818[2, 3, 7, 18]418 在 7 和 101 之间替换 tails[3]18最终 size 4✅重要说明tails数组不是真正的 LIS只是长度相同。例如最后tails [2, 3, 7, 18]但原数组中没有[2,3,7,18]这个子序列7 在 3 后面但 18 在 101 后面。它只是维护了每个长度的最小末尾值。复杂度分析时间复杂度O(n log n) — 每个数二分查找 O(log n)空间复杂度O(n) — tails 数组优缺点✅ 时间复杂度最优 O(n log n)✅ 空间复杂度 O(n)❌ 无法直接得到具体的子序列需要额外处理⭐ 面试推荐写法方法三线段树进阶了解即可思路将数值离散化后使用线段树维护以某个值结尾的 LIS 长度。代码实现简化版javapublic int lengthOfLIS(int[] nums) { // 离散化 int[] sorted nums.clone(); Arrays.sort(sorted); MapInteger, Integer map new HashMap(); for (int i 0; i sorted.length; i) { map.put(sorted[i], i 1); } int n nums.length; int[] tree new int[4 * n 5]; for (int num : nums) { int idx map.get(num); // 查询 [1, idx-1] 的最大值 int maxLen query(tree, 1, 1, n, 1, idx - 1); // 更新 idx 位置为 maxLen 1 update(tree, 1, 1, n, idx, maxLen 1); } return query(tree, 1, 1, n, 1, n); }复杂度分析时间复杂度O(n log n)空间复杂度O(n)优缺点✅ 时间复杂度 O(n log n)✅ 可以处理更复杂的问题如带权重的 LIS❌ 代码复杂面试不常用方法四打印具体的 LIS扩展思路在 DP 的基础上记录前驱节点最后回溯。代码实现javapublic ListInteger lengthOfLISWithSequence(int[] nums) { int n nums.length; int[] dp new int[n]; int[] prev new int[n]; // 记录前驱索引 Arrays.fill(prev, -1); Arrays.fill(dp, 1); int maxLen 1; int maxIdx 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; prev[i] j; } } if (dp[i] maxLen) { maxLen dp[i]; maxIdx i; } } // 回溯构建序列 ListInteger sequence new ArrayList(); while (maxIdx ! -1) { sequence.add(0, nums[maxIdx]); maxIdx prev[maxIdx]; } return sequence; }方法对比总结方法时间复杂度空间复杂度能否得到具体序列推荐度动态规划O(n²)O(n)✅ 可以⭐⭐⭐贪心二分O(n log n)O(n)❌ 需要额外处理⭐⭐⭐⭐⭐线段树O(n log n)O(n)✅ 可以⭐⭐图文详解动态规划过程可视化textnums: 10 9 2 5 3 7 101 18 dp: 1 1 1 2 2 3 4 4 状态转移图箭头表示可以从前面转移过来 10 ← 无 9 ← 无 2 ← 无 5 ← 2 3 ← 2 7 ← 5, 3 101 ← 7, 5, 3, 2, ... 18 ← 7, 5, 3, 2, ...贪心 二分过程可视化texttails 数组的变化每个位置表示长度为 i1 的 LIS 的最小末尾 步骤1: [10] → 长度1的最小末尾:10 步骤2: [9] → 长度1的最小末尾:9更优 步骤3: [2] → 长度1的最小末尾:2更优 步骤4: [2, 5] → 长度2的最小末尾:5 步骤5: [2, 3] → 长度2的最小末尾:3更优 步骤6: [2, 3, 7] → 长度3的最小末尾:7 步骤7: [2, 3, 7, 101] → 长度4的最小末尾:101 步骤8: [2, 3, 7, 18] → 长度4的最小末尾:18更优 最终 tails [2, 3, 7, 18]长度 4常见问题 QAQ1为什么贪心二分是正确的A维护tails[i]表示长度为 i1 的递增子序列的最小末尾。对于新的数x如果x大于所有末尾说明可以扩展最长长度否则找到第一个≥ x的位置并替换这样不会让长度变短但让后面的数更容易接上这是一个经典的贪心证明问题。Q2贪心法能得到正确的 LIS 长度但 tails 数组就是 LIS 吗A不一定是。tails只保证长度正确但元素可能不是原数组中的连续子序列。例如[2, 3, 7, 18]在原数组中并非递增子序列18 在 7 前面需要验证。它只是每个长度的潜力值。Q3如果要求返回具体的 LIS该怎么办A使用 O(n²) 的 DP 并记录前驱或者对贪心法做额外处理维护每个位置的前驱信息。Q4如何处理非严格递增允许相等A将判断条件从nums[j] nums[i]改为nums[j] nums[i]二分查找时找第一个 num的位置。Q5n2500 时 O(n²) 能过吗A2500² 6,250,000 ≈ 6 百万在 Java 中约 0.1 秒可以过。但如果是 n10^5 就不能了。扩展最长递增子序列的变种1. 最长非递减子序列java// 只需将 改为 ≤ if (nums[j] nums[i]) { dp[i] Math.max(dp[i], dp[j] 1); } // 贪心二分找第一个 num 的位置 int pos Arrays.binarySearch(tails, 0, size, num 1);2. 最长递增子序列的个数LeetCode 673需要同时维护长度和个数用两个 DP 数组。3. 俄罗斯套娃信封问题LeetCode 354先按宽度排序再对高度求 LIS。4. 最长数对链LeetCode 646排序后求 LIS 或贪心。总结最长递增子序列是 LeetCode Hot 100 中的经典动态规划题目也是面试高频题。面试建议先说 O(n²) 的 DP 解法基础再优化到 O(n log n) 的贪心二分进阶解释贪心法的核心思想维护每个长度的最小末尾如果问具体序列可以说用 O(n²) 记录前驱核心要点理解 DP 状态定义dp[i]是以nums[i]结尾的 LIS 长度理解贪心二分的核心tails[i]是长度为 i1 的 LIS 的最小末尾掌握二分查找的边界处理一句话总结最长递增子序列可以用 O(n²) 的动态规划求解但更优的是 O(n log n) 的贪心二分维护一个 tails 数组每个新数通过二分找到合适位置替换或追加最终 tails 的长度就是答案。参考链接LeetCode 300. 最长递增子序列 题目链接LeetCode 300. 最长递增子序列 官方题解