300. 最长递增子序列 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/longest-increasing-subsequence/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 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
提示：
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10
进阶： 你能将算法的时间复杂度降低到 O(n log n) 吗？
题目详细分析
- 数据范围：长度最大 2500，O(n²) 的 DP 可通过（6.25M 次操作）。进阶要求 O(n log n) 用贪心 + 二分。
- 核心约束：严格递增（<，不是 <=）。子序列不要求连续，但顺序不能改变。
- 边界条件：数组长度 1 时 LIS 为 1；所有元素相等时 LIS 为 1。
- 隐藏条件：LIS 不一定是唯一的，但只需返回长度。经典的”最长递增子序列”与”最长上升子序列”是同一个问题。
小白版直白理解
给你一排数字，你想从中挑出一些来组成一个”逐步变大”的序列，可以不连续但要保持原来的顺序。比如 [10,9,2,5,3,7,101,18] 中，选 [2,3,7,101] 就是一个递增序列。这就好比逛旧货市场，每个摊位的价格不同，你只能按顺序逛，每次想买一件比上次更贵的商品，问最多能买几件。
解题思路
思路一：动态规划 O(n²)（推荐）
核心洞察：定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。对于每个 i，遍历它前面的所有 j，如果 nums[j] < nums[i]，就可以在 dp[j] 的基础上接上 nums[i]。
DP 五步法：
- dp 定义：
dp[i]表示以 nums[i] 结尾的 LIS 长度 - 递推公式：
dp[i] = max(dp[i], dp[j] + 1)for j < i if nums[j] < nums[i] - 初始化：所有
dp[i] = 1（至少包含自身） - 遍历顺序：从左到右，内层 j 从 0 到 i-1
- 举例验证：nums=[10,9,2,5,3,7,101,18] → dp[0]=1, dp[1]=1, dp[2]=1, dp[3]=max(1,1+1)=2, dp[4]=max(1,1+1)=2, dp[5]=max(1,2+1,2+1)=3, dp[6]=4, dp[7]=4 ✓
def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # 至少包含自身
for i in range(n):
for j in range(i): # 枚举 i 前面的元素
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 取所有位置结尾的最大值思路二：贪心 + 二分 O(n log n)（进阶）
核心洞察：维护数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。用二分找到 num 在 tails 中的插入位置，替换或追加。
import bisect
def lengthOfLIS(nums):
tails = [] # tails[i] = 长度为 i+1 的 LIS 的最小末尾
for num in nums:
i = bisect.bisect_left(tails, num) # 二分查找插入位置
if i == len(tails):
tails.append(num) # num 比所有末尾大，延长 LIS
else:
tails[i] = num # 替换，让尾部更小
return len(tails)思路三：耐心排序 Patience Sorting（思路二可视化解释）
想象你要按顺序排一堆扑克牌，每张牌能放到”最左边比它大的牌堆”上。最后牌堆数就是 LIS 长度。
def lengthOfLIS(nums):
piles = [] # 每个牌堆的堆顶牌
for num in nums:
# 找到最左边堆顶 >= num 的牌堆
i = bisect.bisect_left(piles, num)
if i == len(piles):
piles.append(num) # 新建一堆
else:
piles[i] = num # 放在该堆顶部
return len(piles)易错点
- dp[i] 定义：是以 nums[i] 结尾，不是”前 i 个”！所以最后返回
max(dp)不是dp[-1]。 - 初始化：所有 dp[i] 至少是 1，不要初始化为 0。
- 严格递增：条件是
<不是<=。 - 二分查找用 bisect_left：需要严格递增时用 bisect_left；如果允许相等（非严格），用 bisect_right。
- tails 数组的含义：tails 不是 LIS 本身，只是存储最小末尾值的辅助数组。
框架提炼
子序列 DP 模板（O(n²)）：
def subsequence_dp(nums):
n = len(nums)
dp = [1] * n # 初始值根据题意
for i in range(n):
for j in range(i): # 枚举转移来源
if condition(nums[j], nums[i]): # 满足某种关系
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)贪心 + 二分模板（O(n log n)）：
def patience_sorting(nums):
tails = []
for num in nums:
i = bisect.bisect_left(tails, num)
if i == len(tails):
tails.append(num)
else:
tails[i] = num
return len(tails)关联题目
- 152-乘积最大子数组 — 子数组 DP 与子序列 DP 的区别
- 1143-最长公共子序列 — 二维子序列 DP，思想扩展
- 354-俄罗斯套娃信封问题 — 二维 LIS，先排序再对另一维求 LIS