最长上升子序列
这是一道围绕数组展开的高频练习。建议先掌握「贪心算法+二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
题目分析
给你一个整数数组，要求找到其中最长严格递增子序列的长度。
这里的“子序列”不要求连续，只要求相对顺序不变。
比如 [10,9,2,5,3,7,101,18] 的最长上升子序列长度是 4，例如 [2,3,7,101]。
一句话概括：
在不要求连续的前提下，找出最长的严格递增序列长度。
推荐代码
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用贪心加二分，把复杂度从 O(n^2) 优化到 O(n log n)。
核心过程
- 维护一个
tails数组，表示不同长度递增子序列的最小结尾。 - 遍历每个数字时，用二分找到它在
tails中应该替换的位置。 - 如果它比当前所有结尾都大，就把最长长度加一。
- 最终
tails的有效长度，就是最长递增子序列长度。
复杂度总结
时间复杂度 O(n log n)，空间复杂度 O(n)。
核心思路
LIS 最难理解的点，是数组 tails 存的不是某条真实子序列，而是“长度固定时尽量小的结尾”。结尾越小，后面越容易接出更长序列。
步骤讲解
维护不同长度序列的最小结尾
用 tails[len] 记录长度为 len + 1 的递增子序列里，能做到的最小结尾值。
用二分找到当前数该落的位置
对每个新数字，在 tails 中找第一个大于等于它的位置并替换。
如果落在末尾就扩展最长长度
当当前数字比所有结尾都大时，它可以接在最长序列后面，让长度加一。
易错点
把 tails 误当成真实 LIS
它只是每个长度下的最优结尾摘要，不保证本身就是一条合法子序列。
tails 的含义是“最小结尾”，不是答案路径。二分条件写成严格大于
这会让相等元素处理错误，影响严格递增条件。
>= num 的位置进行替换。只会背 DP，不会解释贪心合理性
这题高频追问就是为什么替换较大结尾不会丢掉答案。
复杂度与适用判断
O(n^2) 更优，面试里也更能体现优化能力。额外提醒
tails存的是摘要状态，不是完整答案路径。
其他语言 / 其他解法
动态规划
动态规划算法求解最长递增子序列：
- 定义状态：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
- 状态转移方程：对于每个 i，遍历 j 从 0 到 i-1，如果 nums[i] > nums[j]，则 dp[i] = max(dp[i], dp[j] + 1)
- 初始状态：所有 dp[i] 初始化为 1，因为每个元素自身可以构成一个长度为 1 的递增子序列
- 最终结果：遍历整个 dp 数组，取最大值即为最长递增子序列的长度
该算法的时间复杂度为 O(n²)，空间复杂度为 O(n)。
动态规划
动态规划算法求解最长递增子序列：
该算法的时间复杂度为 O(n²)，空间复杂度为 O(n)。
- 定义状态：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
- 状态转移方程：对于每个 i，遍历 j 从 0 到 i-1，如果 nums[i] > nums[j]，则 dp[i] = max(dp[i], dp[j] + 1)
- 初始状态：所有 dp[i] 初始化为 1，因为每个元素自身可以构成一个长度为 1 的递增子序列
- 最终结果：遍历整个 dp 数组，取最大值即为最长递增子序列的长度
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
动画演示
如果你还没完全看懂，可以展开动画演示。
贪心算法+二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
贪心算法+二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。