企业官网建设流程全解析

LeetCode-Book 精讲：最长递增子序列（LIS）——从 O(N²) 动态规划到 O(NlogN) 二分优化

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本文以 LeetCode-Book 仓库中《Krahets 笔面试精选 88 题》的「最长递增子序列」题解为主体，系统讲解该题的两套经典解法：O(N²) 的常规动态规划，以及通过重新设计状态定义将复杂度降至 O(NlogN) 的动态规划 + 二分查找。读完本文，你将掌握 LIS 问题「状态定义 → 转移方程 → 复杂度优化」的完整分析链路，理解二分优化背后的数学直觉，并能直接运行仓库中给出的 Python / Java 源码进行验证。

一、题目概述：什么是最长递增子序列

「最长递增子序列」（Longest Increasing Subsequence，LIS）是动态规划领域的经典入门题目（LeetCode 300 题），也是《Krahets 笔面试精选 88 题》中的高频考点。题目要求：给定一个无序整数数组nums，找到其中最长严格递增子序列的长度。

理解此题必须抓住两个关键点：

• 子序列 ≠ 子数组：子序列不要求元素在原数组中连续，只需保持相对顺序即可。例如[10, 9, 2, 5, 3, 7, 101, 18]中，[2, 3, 7, 101]就是一个合法的递增子序列，尽管它在原数组中并不连续。
• 严格递增：要求nums[i] > nums[j]（后一个元素严格大于前一个），即不允许相等元素相邻构成递增关系。

原题解文档位于 selected_coding_interview/docs/300. 最长递增子序列.md，对应的可运行代码在 Python 源码 与 Java 源码 中，下文将逐一展开。

二、解法一：动态规划（O(N²)）

这是最直观、最符合 DP 学习路径的解法：枚举每个元素作为「子序列结尾」的所有可能，逐步累积出全局最优解。

2.1 状态定义

定义dp[i]为以nums[i]结尾的最长递增子序列的长度。注意这里的状态不是"全局最长"，而是"强制以第 i 个元素收尾"，这是后续转移能够成立的关键。

2.2 转移方程

设j ∈ [0, i)，计算每个新的dp[i]时，遍历[0, i)区间内的所有元素，逐一判断：

1. 当nums[i] > nums[j]时：nums[i]可以接在nums[j]之后（题目要求严格递增），此时以nums[i]结尾的子序列长度为dp[j] + 1；
2. 当nums[i] <= nums[j]时：nums[i]无法接在nums[j]之后，该情况不构成递增子序列，跳过。

对上述所有第 1 种情况求最大值，即为dp[i]的最终取值。实现时只需在遍历j的每一轮执行：

dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)

2.3 初始状态与返回值

• 初始状态：dp[i]所有元素初始化为1。含义是每个元素自身至少可以单独构成一个长度为 1 的递增子序列。
• 返回值：返回dp列表的最大值，即全局最长递增子序列的长度。

2.4 复杂度分析

• 时间复杂度 O(N²)：遍历计算dp列表需 O(N)，计算每个dp[i]又需遍历[0, i)区间 O(N)，总复杂度 O(N²)。
• 空间复杂度 O(N)：dp列表占用线性大小的额外空间。

2.5 代码实现

仓库中的 Python 与 Java 实现与原文档一致，可直接运行验证：

# Dynamic programming. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。 dp[i] = max(dp[i], dp[j] + 1) return max(dp)

// Dynamic programming. class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0) return 0; int[] dp = new int[nums.length]; int res = 0; Arrays.fill(dp, 1); for(int i = 0; i < nums.length; i++) { for(int j = 0; j < i; j++) { if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } res = Math.max(res, dp[i]); } return res; } }

对应仓库文件：Python 解法一、Java 解法一。仓库为两种解法都附带了完整的测试驱动代码（# ====== Test Case ======与main方法），测试输入为[1, 2, 3, 4, 5]，期望输出5，可直接运行查看结果。

2.6 手推示例

以nums = [10, 9, 2, 5, 3, 7, 101, 18]为例逐步推演：

最终max(dp) = 5，即最长递增子序列[2, 5, 7, 101]（或[2, 3, 7, 18]）的长度。

三、解法二：动态规划 + 二分查找（O(NlogN)）

解法一在N很大时会超时，因此需要优化。优化思路不能简单套模板，而要重新审视状态定义本身。

3.1 优化切入点：复杂度从何而来

回顾解法一的两层循环：

1. 外层遍历计算所有dp值需要 O(N)，这是无法避免的；
2. 内层为计算每个dp[k]需要线性遍历[0, k)区间，共 O(N)。

那么关键问题就变成了：能否重新设计状态定义，使得用于转移的辅助列表天然有序，从而把内层遍历从 O(N) 降为 O(logN)？

3.2 新的状态定义：tails 列表

维护一个列表tails，其中tails[k]表示长度为k+1的递增子序列的尾部元素值。例如序列[1, 4, 6]，长度为 1、2、3 的子序列尾部元素值分别为tails = [1, 4, 6]。

tails并不直接等于某个具体的递增子序列，它只记录"各类长度的子序列在最优选择下的尾部最小值"，其长度res即当前已知的最长递增子序列长度。

3.3 贪心直觉：尾部元素越小越好

为什么遍历时要不断更新、始终保持每个尾部元素值最小？原因很简单：

设常量数字N和随机数字x，当N越小时，N < x的概率越大。例如N = 0一定比N = 1000更可能满足N < x。

对应到算法中：在遍历计算每个tails[k]时，不断更新长度为[1, k]的子序列尾部元素值，始终保持每个尾部元素值最小。例如序列[1, 5, 3]：

• 遍历到元素5时，长度为 2 的子序列尾部元素值为5（此时tails = [1, 5]）；
• 遍历到元素3时，应把尾部元素值更新为3（tails = [1, 3]），因为3比5遇到比它更大的数字的几率更大，更有利于后续接出更长的序列。

3.4 tails 必然严格递增（反证法证明）

这是二分查找能够应用的前提，也是本解法最精妙的推理：

命题：在尽量使每个子序列尾部元素值最小的前提下，子序列越长，其尾部元素值一定更大，即tails严格递增。

反证法：假设k < i时存在tails[k] >= tails[i]，意味着较短的子序列尾部元素值不小于较长的子序列尾部元素值。但从长度为i的子序列尾部倒序删除i - 1个元素，剩下的就是长度为k的子序列，设其尾部元素值为v，则一定有v < tails[i]（长度为 k 的子序列尾部元素值必然更小），这与tails[k] >= tails[i]矛盾。因此假设不成立，tails必然严格递增。

既然tails严格递增，每轮计算时就可以用二分查找快速定位需要更新的尾部元素索引。

3.5 算法流程

• 状态定义：tails[k]表示长度为k+1的递增子序列的尾部元素值。
• 转移方程：设res为tails当前长度（即当前已知的最长递增子序列长度），每轮遍历nums[k]时，在[0, res)区间二分查找nums[k]的大小分界点：
  • 区间中存在tails[i] > nums[k]：将第一个满足tails[i] > nums[k]的元素更新为nums[k]（即tails[i] = nums[k]），因为更小的尾部元素后更可能接上更大的数字；
  • 区间中不存在tails[i] > nums[k]：说明nums[k]可以接在目前所有长度的子序列之后，最优策略是接到最长序列（长度为res）后面，形成长度为res + 1的新子序列。
• 初始状态：tails列表所有值初始化为0（Java 中 int 数组默认即全 0）。
• 返回值：返回res，即最长递增子序列的长度。

3.6 复杂度分析

• 时间复杂度 O(NlogN)：遍历nums需 O(N)，每个nums[i]的二分查找需 O(logN)。
• 空间复杂度 O(N)：tails列表占用线性大小的额外空间。

3.7 代码实现

# Dynamic programming + Dichotomy. class Solution: def lengthOfLIS(self, nums: [int]) -> int: tails, res = [0] * len(nums), 0 for num in nums: i, j = 0, res while i < j: m = (i + j) // 2 if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。 else: j = m tails[i] = num if j == res: res += 1 return res

// Dynamic programming + Dichotomy. class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int res = 0; for(int num : nums) { int i = 0, j = res; while(i < j) { int m = (i + j) / 2; if(tails[m] < num) i = m + 1; else j = m; } tails[i] = num; if(res == j) res++; } return res; } }

对应仓库文件：Python 解法二、Java 解法二。

3.8 二分过程手推

仍以nums = [10, 9, 2, 5, 3, 7, 101, 18]为例：

最终res = 4。注意此示例中解法一与解法二结果一致（均为 4），说明两种算法在求长度上等价；需要强调的是tails本身并不对应真实的最长递增子序列，它只是记录了各长度下最有利的尾部值。

四、两种解法对比与实战选择

实战建议：面试时先流畅给出 O(N²) 动态规划解法（包含状态定义、转移方程、初始状态、返回值四要素），再主动提出可以用"贪心 + 二分"优化到 O(NlogN)，并讲清tails严格递增的反证法证明——这正是本题区分度最高的考察点。原文档也按此顺序组织两种解法，从 题解文档 可直接对照学习。

五、进阶拓展

5.1 非严格递增变体：只改一行

两道代码注释中都明确提示了变体改法：

如果要求非严格递增，将此行'<'改为'<='即可。

• 解法一中：if nums[j] < nums[i]:改为if nums[j] <= nums[i]:；
• 解法二中：if tails[m] < num: i = m + 1改为if tails[m] <= num: i = m + 1。

原因在于：非严格递增允许相等元素相接，二分查找时相等值不应视为"需要替换的更大元素"，而是应继续向右搜索以接在等值元素之后，从而正确统计长度。

5.2 如何重构出具体的最长递增子序列

题目只要求返回长度，但面试中常被追问能否输出具体序列。可以推断有两种常见扩展思路：

1. 回溯法（配合 O(N²) DP）：在计算dp[i]时记录pre[i] = j（转移来源下标），最后从dp最大值位置沿pre链回溯即可还原序列；
2. 贪心二分法（配合 O(NlogN) 解法）：额外维护idx数组记录每个tails元素在原数组中的下标，并用pre数组记录更新时的前驱下标，同样可还原出一个合法的最长递增子序列。

5.3 仓库内相关 DP 题目联动

LIS 属于"线性 DP / 序列 DP"的经典范式，仓库中还收录了多道可对比练习的动态规划题目，适合串联复习：

• 最大子数组和（剑指 Offer 42 与 LCR 161）：同样是定义"以 i 结尾"的 DP，但转移只依赖前一项，复杂度可做到 O(N)；
• 打家劫舍（198. 打家劫舍）与打家劫舍 II（213. 打家劫舍 II）：掌握"状态机 DP + 环形处理"；
• 整数拆分（343. 整数拆分）：理解"枚举切割点"式的区间转移；
• 最小路径和（64. 最小路径和）：二维 DP 的入门代表。

六、小结

「最长递增子序列」一题完整覆盖了动态规划的四个标准步骤（状态定义、转移方程、初始状态、返回值），又通过重新设计状态引入了"贪心 + 二分"这一高频优化技巧，是训练面试算法思维的极佳载体。建议在 LeetCode-Book 仓库中对照 题解文档 通读推理过程，再运行仓库中的 Python 与 Java 源码验证结果，最后尝试自行推导非严格递增变体与序列重构，做到举一反三。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book