知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 最长递增子序列(LIS) ## 题目(LeetCode 300) 找出数组中最长严格递增子序列的长度。子序列不要求连续,但要保持相对顺序。 ``` 输入:[10, 9, 2, 5, 3, 7, 101, 18] 输出:4(比如 [2, 3, 7, 101] 或 [2, 5, 7, 101]) ``` ## 先搞清楚"子序列"是什么 ``` 原数组:[10, 9, 2, 5, 3, 7, 101, 18] 子序列:从原数组中挑一些元素,保持原来的先后顺序 [10, 5, 101] ✓ 子序列(顺序没变) [2, 5, 7, 101] ✓ 子序列,而且是递增的 [5, 2, 7] ✗ 不是子序列(5 在 2 前面,顺序变了) 子序列 ≠ 子数组: 子数组必须连续:[2, 5, 3] 是子数组 子序列可以跳着选:[2, 5, 7] 是子序列但不是子数组 ``` --- ## 解法一:DP — O(n²) ### 核心思想:站在每个位置往回看 想象你站在数组的每个位置上,回头看前面所有比你小的数,问自己: > "我接在谁后面,能让递增子序列最长?" ``` dp[i] 的含义:以 nums[i] 结尾的最长递增子序列的长度 为什么要"以 nums[i] 结尾"? 因为后面的数要接在前面的后面,必须知道前面的子序列是以谁结尾的 只有知道结尾是几,才能判断后面的数能不能接上去 ``` ### 转移方程 ``` 对于位置 i,遍历它前面的所有位置 j(j < i): 如果 nums[j] < nums[i](j 位置的数比 i 小,可以接上去) dp[i] = max(dp[i], dp[j] + 1) 翻译成人话: "我(位置 i)看看前面每个比我小的数(位置 j), 它们各自能组成多长的递增子序列(dp[j]), 我接在最长的那个后面,长度就是 dp[j] + 1" ``` ### 手动模拟(这是理解的关键) ``` nums = [10, 9, 2, 5, 3, 7, 101, 18] dp = [ 1, 1, 1, 1, 1, 1, 1, 1] ← 初始化全为 1(自己就是长度 1) 处理 i=0 (nums[0]=10): 前面没有数 → dp[0] = 1 dp = [1, 1, 1, 1, 1, 1, 1, 1] 处理 i=1 (nums[1]=9): 看 j=0: nums[0]=10 > 9 → 不能接(10 比 9 大,不是递增) 没有能接的 → dp[1] = 1 dp = [1, 1, 1, 1, 1, 1, 1, 1] 处理 i=2 (nums[2]=2): 看 j=0: nums[0]=10 > 2 → 不能接 看 j=1: nums[1]=9 > 2 → 不能接 dp[2] = 1 dp = [1, 1, 1, 1, 1, 1, 1, 1] 处理 i=3 (nums[3]=5): 看 j=0: nums[0]=10 > 5 → 不能接 看 j=1: nums[1]=9 > 5 → 不能接 看 j=2: nums[2]=2 < 5 → 能接!dp[3] = max(1, dp[2]+1) = max(1, 2) = 2 dp = [1, 1, 1, 2, 1, 1, 1, 1] 含义:以 5 结尾的 LIS 是 [2, 5],长度 2 处理 i=4 (nums[4]=3): 看 j=0: 10 > 3 → 不能接 看 j=1: 9 > 3 → 不能接 看 j=2: 2 < 3 → 能接!dp[4] = max(1, dp[2]+1) = 2 看 j=3: 5 > 3 → 不能接 dp = [1, 1, 1, 2, 2, 1, 1, 1] 含义:以 3 结尾的 LIS 是 [2, 3],长度 2 处理 i=5 (nums[5]=7): 看 j=0: 10 > 7 → 不能接 看 j=1: 9 > 7 → 不能接 看 j=2: 2 < 7 → 能接!dp[5] = max(1, 1+1) = 2 看 j=3: 5 < 7 → 能接!dp[5] = max(2, 2+1) = 3 ← 接在 [2,5] 后面更长 看 j=4: 3 < 7 → 能接!dp[5] = max(3, 2+1) = 3 ← 接在 [2,3] 后面一样长 dp = [1, 1, 1, 2, 2, 3, 1, 1] 含义:以 7 结尾的 LIS 是 [2, 5, 7] 或 [2, 3, 7],长度 3 处理 i=6 (nums[6]=101): 2 < 101 → dp[6] = max(1, 1+1) = 2 5 < 101 → dp[6] = max(2, 2+1) = 3 3 < 101 → dp[6] = max(3, 2+1) = 3 7 < 101 → dp[6] = max(3, 3+1) = 4 ← 接在 [2,5,7] 后面 dp = [1, 1, 1, 2, 2, 3, 4, 1] 含义:以 101 结尾的 LIS 是 [2, 5, 7, 101],长度 4 处理 i=7 (nums[7]=18): 2 < 18 → dp[7] = 2 5 < 18 → dp[7] = 3 3 < 18 → dp[7] = 3 7 < 18 → dp[7] = max(3, 3+1) = 4 ← 接在 [2,5,7] 后面 101 > 18 → 不能接 dp = [1, 1, 1, 2, 2, 3, 4, 4] 最终答案 = max(dp) = 4 ✓ ``` ### 代码 ```java public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); // 每个元素自身就是长度 1 的子序列 int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } ``` 时间 O(n²),空间 O(n)。 --- ## 解法二:贪心 + 二分 — O(n log n) ### 核心思想:用一个生活例子理解 想象你在玩一个纸牌游戏: ``` 规则: 桌上有若干堆牌,每堆从下到上递增 新来一张牌,放到第一个"堆顶 ≥ 这张牌"的堆上 如果所有堆顶都比这张牌小,就新开一堆 堆的数量 = 最长递增子序列的长度 ``` 为什么?因为每一堆代表"在这个长度的递增子序列中,末尾最小能是多少"。 ### 换个说法 维护一个数组 `tails`: - `tails[0]` = 长度为 1 的递增子序列,末尾最小是多少 - `tails[1]` = 长度为 2 的递增子序列,末尾最小是多少 - `tails[2]` = 长度为 3 的递增子序列,末尾最小是多少 - ... ``` 关键性质:tails 数组一定是递增的 为什么? 长度为 2 的递增子序列的末尾,一定比长度为 1 的大 (因为长度为 2 的子序列 = 长度为 1 的子序列 + 一个更大的数) ``` ### 对于每个新数 num,做两件事之一 ``` 情况 1:num 比 tails 中所有数都大 → 可以接在最长的子序列后面,LIS 长度 +1 → tails 末尾追加 num 情况 2:num 不是最大的 → 找到 tails 中第一个 ≥ num 的位置,替换它 → 含义:同样长度的子序列,末尾可以更小了(给未来留更多空间) → 用二分查找,O(log n) ``` ### 手动模拟(逐步理解) ``` nums = [10, 9, 2, 5, 3, 7, 101, 18] tails = [] 处理 10:tails 为空,直接加入 tails = [10] 含义:长度 1 的 LIS 末尾最小是 10 处理 9:9 < 10,替换 tails 中第一个 ≥ 9 的数(就是 10) tails = [9] 含义:长度 1 的 LIS 末尾最小是 9(比 10 更好,因为 9 更小,后面更容易接上) 处理 2:2 < 9,替换 9 tails = [2] 含义:长度 1 的 LIS 末尾最小是 2(更好了) 处理 5:5 > 2(比所有都大),追加 tails = [2, 5] 含义:长度 1 末尾最小 2,长度 2 末尾最小 5 对应子序列:[2, 5] 处理 3:3 在 2 和 5 之间,替换第一个 ≥ 3 的数(5) tails = [2, 3] 含义:长度 2 的 LIS 末尾最小从 5 变成了 3(更好了) 对应子序列:[2, 3](比 [2, 5] 更有潜力,因为 3 后面能接的数更多) 处理 7:7 > 3(比所有都大),追加 tails = [2, 3, 7] 含义:长度 3 末尾最小 7 对应子序列:[2, 3, 7] 处理 101:101 > 7,追加 tails = [2, 3, 7, 101] 含义:长度 4 末尾最小 101 对应子序列:[2, 3, 7, 101] 处理 18:18 在 7 和 101 之间,替换 101 tails = [2, 3, 7, 18] 含义:长度 4 的 LIS 末尾最小从 101 变成了 18(更好了) 最终 tails 长度 = 4 → LIS 长度 = 4 ✓ ``` ### 为什么"替换"不会影响正确性? ``` 这是最容易困惑的地方。 替换不会改变当前的 LIS 长度,它只是在"优化未来的可能性"。 比如 tails 从 [2, 5] 变成 [2, 3]: LIS 长度还是 2,没变 但末尾从 5 变成了 3 后面如果来一个 4,[2, 3] 能接上变成 [2, 3, 4] 而 [2, 5] 接不上(4 < 5) 替换 = 不改变现在,但为未来创造更多可能 ``` ### 注意:tails 不是实际的 LIS ``` tails = [2, 3, 7, 18] 不代表 LIS 就是 [2, 3, 7, 18] 实际的 LIS 可能是 [2, 5, 7, 101] 或 [2, 3, 7, 101] tails 只是用来计算长度的辅助数组 如果需要输出实际的 LIS,需要额外记录每个元素的来源 ``` ### 代码 ```java public int lengthOfLIS(int[] nums) { List<Integer> tails = new ArrayList<>(); for (int num : nums) { // 二分查找:找 tails 中第一个 >= num 的位置 int left = 0, right = tails.size(); while (left < right) { int mid = (left + right) / 2; if (tails.get(mid) < num) { left = mid + 1; } else { right = mid; } } if (left == tails.size()) { tails.add(num); // 比所有都大,追加 } else { tails.set(left, num); // 替换 } } return tails.size(); } ``` 时间 O(n log n),空间 O(n)。 --- ## 两种解法对比 ``` 解法 时间 空间 理解难度 适用场景 DP O(n²) O(n) 容易 n ≤ 2500 贪心+二分 O(n log n) O(n) 较难 n ≤ 10^5 面试中两种都要会: DP 解法展示你理解动态规划 贪心+二分展示你能优化 ``` ## 一句话总结 DP 解法:每个位置往回看,找前面比自己小的最长子序列接上去。贪心+二分:维护一个"每种长度的最小末尾"数组,新数要么扩展长度,要么替换让末尾更小。 --- 上一篇:[03 - 打家劫舍](./03-house-robber.md) | 下一篇:[05 - 零钱兑换](./05-coin-change.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入