最长上升子序列（LIS）问题
字数 3641 2025-12-08 16:11:55

最长上升子序列（LIS）问题

最长上升子序列（Longest Increasing Subsequence，LIS）问题是这样一个经典动态规划问题：
给定一个长度为 n 的整数数组 nums，找到其中严格递增（通常，严格递增指的是 nums[i] < nums[i+1]）的最长子序列的长度。这里的“子序列”不要求连续，只要保持原数组中的相对顺序即可。

例如：
输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出：4
解释：最长的上升子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18]，长度都是 4。

下面我将循序渐进地讲解两种主流的解法。

解法一：动态规划（O(n²)）

这是最直观的动态规划思路。关键在于如何定义状态。

1. 定义状态
我们可以定义一个一维数组 dp，其中 dp[i] 表示以第 i 个数字（nums[i]）为结尾的最长上升子序列的长度。

为什么是“以某个位置为结尾”？
因为子序列要求递增，当我们计算到 nums[i] 时，需要看它能否接在之前某个子序列的后面，从而形成一个更长的子序列。如果定义“以 i 为开头”，则后续状态不容易利用前面的结果。

2. 推导状态转移方程
对于 dp[i]，我们需要考察在 i 之前的所有位置 j (0 ≤ j < i)。

  • 如果 nums[i] > nums[j]，说明 nums[i] 可以接在“以 nums[j] 为结尾”的上升子序列后面，形成一个长度为 dp[j] + 1 的新子序列。
  • 我们需要找到所有满足条件的 j 中，能得到的最大长度。
    因此，状态转移方程为：
    dp[i] = max(dp[j]) + 1, 对于所有满足 nums[j] < nums[i] 的 j (0 ≤ j < i)
    如果对于所有 j 都不满足 nums[i] > nums[j]，那么以 nums[i] 结尾的上升子序列就只包含它自己，即 dp[i] = 1。

3. 确定初始状态
对于任何一个位置，最起码可以以自己作为一个长度为 1 的子序列。所以，所有的 dp[i] 初始值都可以设为 1。

4. 计算顺序与最终结果
由于计算 dp[i] 需要用到 i 之前所有位置的 dp 值，所以我们应从左到右计算 i 从 0 到 n-1 的 dp 值。

最终结果并不是 dp[n-1]，因为最长的上升子序列不一定以最后一个元素结尾。最终结果应该是 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1])。

5. 算法步骤示例
以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：

  • 初始化 dp 数组全为 1: dp = [1, 1, 1, 1, 1, 1, 1, 1]
  • i=0: 前面没有元素，dp[0] 保持为 1。
  • i=1 (nums[1]=9): 比较 j=0(10)，9<10 不满足，dp[1]=1
  • i=2 (nums[2]=2): 比较 j=0(10), j=1(9)，都更大，dp[2]=1
  • i=3 (nums[3]=5): 比较 j=0(10>5)，j=1(9>5)，j=2(2<5)。只有 j=2 满足，dp[3] = dp[2]+1 = 2
  • i=4 (nums[4]=3): 只有 j=2(2<3) 满足，dp[4] = dp[2]+1 = 2
  • i=5 (nums[5]=7): 可接在 j=2(dp=1)，j=3(dp=2)，j=4(dp=2) 后面。最大 dp 值是2，所以 dp[5] = 2+1 = 3
  • i=6 (nums[6]=101): 可接在 j=0,1,2,3,4,5 后面，其中 dp[5]=3 最大，所以 dp[6] = 3+1 = 4
  • i=7 (nums[7]=18): 同样可接在多个位置后，dp[5]=3 最大，所以 dp[7] = 3+1 = 4
    最终，dp = [1, 1, 1, 2, 2, 3, 4, 4]，最大值为 4。

复杂度分析
时间复杂度：O(n²)，因为有双层循环（i 从 0 到 n-1，对于每个 i，j 从 0 到 i-1）。
空间复杂度：O(n)，用于存储 dp 数组。

解法二：贪心 + 二分查找（O(n log n)）

这种方法是更优的解法，也是面试中的考察重点。其核心思想是：让序列上升得尽可能慢，这样后面才有更多机会接上更长的序列。

1. 核心思路
我们维护一个数组 tail（或 low）。tail[i] 的定义是：所有长度为 i+1 的上升子序列中，结尾数字最小的那个值。
为什么记录最小结尾数字？因为对于相同长度的上升子序列，结尾数字越小，将来扩展时能接上更大数字的可能性就越大，潜力就越大。

2. 算法过程

  • 初始化：tail 为空数组。
  • 遍历原数组 nums 中的每个数字 x：
    1. 在 tail 数组中寻找第一个大于等于 x 的数字的位置。这可以使用二分查找实现。
    2. 如果找到了这个位置（设为 pos）：
      • 用 x 替换 tail[pos]。因为 tail[pos] 是长度为 pos+1 的子序列的最小结尾，现在找到了一个更小的结尾 x，所以更新它。
    3. 如果没找到（即 x 大于 tail 中的所有元素）：
      • 将 x 添加到 tail 的末尾。这意味着我们找到了一个更长的上升子序列（长度为当前 tail.length + 1），并且其结尾是 x。
  • 遍历结束后，tail 数组的长度就是最长上升子序列的长度。

3. 算法步骤示例
再次以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：

  • 初始化 tail = []
  • 处理 10: tail为空，直接加入。tail = [10]
  • 处理 9: 在 tail=[10] 中二分查找第一个 ≥9 的元素，是 10 (pos=0)。替换。tail = [9] （长度为1的子序列，最小结尾从10更新为9）
  • 处理 2: 在 tail=[9] 中二分查找第一个 ≥2 的元素，是 9 (pos=0)。替换。tail = [2]
  • 处理 5: 在 tail=[2] 中二分查找第一个 ≥5 的元素，没找到（5>2）。添加到末尾。tail = [2, 5]
  • 处理 3: 在 tail=[2,5] 中二分查找第一个 ≥3 的元素，是 5 (pos=1)。替换。tail = [2, 3]（长度为2的子序列，最小结尾从5更新为3）
  • 处理 7: 在 tail=[2,3] 中二分查找第一个 ≥7 的元素，没找到（7>3）。添加到末尾。tail = [2, 3, 7]
  • 处理 101: 在 tail=[2,3,7] 中二分查找第一个 ≥101 的元素，没找到。添加到末尾。tail = [2, 3, 7, 101]
  • 处理 18: 在 tail=[2,3,7,101] 中二分查找第一个 ≥18 的元素，是 101 (pos=3)。替换。tail = [2, 3, 7, 18]
    遍历结束，tail 的长度为 4，即 LIS 长度为 4。

4. 关键点与理解

  • tail 数组本身不一定是原数组的一个子序列！例如，当 tail 从 [2,5] 变为 [2,3] 时，3 出现在 5 之后，但在原数组中 3 在 5 之前。tail 数组只是用来记录“每个长度的最小结尾”，它的长度才是我们想要的结果。
  • 二分查找在这里的作用是快速定位当前数字 x 在 tail 数组中的合适位置。查找条件（第一个 ≥ x 的元素）使得算法能够正确维护“最小结尾”的性质。

复杂度分析
时间复杂度：O(n log n)。遍历 n 个元素，每个元素用 O(log n) 时间进行二分查找和可能的替换。
空间复杂度：O(n)，最坏情况下 tail 数组长度等于原数组长度。

总结
最长上升子序列问题有两种经典解法：

  1. 动态规划 (O(n²))：思路直接，易于理解和实现，适用于小规模数据或作为思路引导。
  2. 贪心+二分 (O(n log n))：效率更高，是面试中期望回答的最优解。核心在于维护一个“长度-最小结尾”数组，并利用二分查找快速更新它，其最终长度即为答案。你需要理解为什么这个方法可行，并能清晰解释 tail 数组的含义和更新逻辑。
最长上升子序列（LIS）问题 最长上升子序列（Longest Increasing Subsequence，LIS）问题是这样一个经典动态规划问题： 给定一个长度为 n 的整数数组 nums ，找到其中严格递增（通常，严格递增指的是 nums[i] < nums[i+1] ）的最长子序列的长度。这里的“子序列”不要求连续，只要保持原数组中的相对顺序即可。 例如： 输入： nums = [10, 9, 2, 5, 3, 7, 101, 18] 输出：4 解释：最长的上升子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18] ，长度都是 4。 下面我将循序渐进地讲解两种主流的解法。 解法一：动态规划（O(n²)） 这是最直观的动态规划思路。关键在于如何定义状态。 1. 定义状态 我们可以定义一个一维数组 dp ，其中 dp[i] 表示以 第 i 个数字 （ nums[i] ） 为结尾 的最长上升子序列的长度。 为什么是“以某个位置为结尾”？ 因为子序列要求递增，当我们计算到 nums[i] 时，需要看它能否接在之前某个子序列的后面，从而形成一个更长的子序列。如果定义“以 i 为开头”，则后续状态不容易利用前面的结果。 2. 推导状态转移方程 对于 dp[i] ，我们需要考察在 i 之前的所有位置 j (0 ≤ j < i)。 如果 nums[i] > nums[j] ，说明 nums[i] 可以接在“以 nums[j] 为结尾”的上升子序列后面，形成一个长度为 dp[j] + 1 的新子序列。 我们需要找到所有满足条件的 j 中，能得到的最大长度。 因此，状态转移方程为： dp[i] = max(dp[j]) + 1, 对于所有满足 nums[j] < nums[i] 的 j (0 ≤ j < i) 如果对于所有 j 都不满足 nums[i] > nums[j] ，那么以 nums[i] 结尾的上升子序列就只包含它自己，即 dp[i] = 1 。 3. 确定初始状态 对于任何一个位置，最起码可以以自己作为一个长度为 1 的子序列。所以，所有的 dp[i] 初始值都可以设为 1。 4. 计算顺序与最终结果 由于计算 dp[i] 需要用到 i 之前所有位置的 dp 值，所以我们应 从左到右 计算 i 从 0 到 n-1 的 dp 值。 最终结果并不是 dp[n-1] ，因为最长的上升子序列不一定以最后一个元素结尾。最终结果应该是 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1]) 。 5. 算法步骤示例 以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例： 初始化 dp 数组全为 1: dp = [1, 1, 1, 1, 1, 1, 1, 1] i=0: 前面没有元素， dp[0] 保持为 1。 i=1 ( nums[1]=9 ): 比较 j=0(10)，9<10 不满足， dp[1]=1 i=2 ( nums[2]=2 ): 比较 j=0(10), j=1(9)，都更大， dp[2]=1 i=3 ( nums[3]=5 ): 比较 j=0(10>5)，j=1(9>5)，j=2(2<5)。只有 j=2 满足， dp[3] = dp[2]+1 = 2 i=4 ( nums[4]=3 ): 只有 j=2(2<3) 满足， dp[4] = dp[2]+1 = 2 i=5 ( nums[5]=7 ): 可接在 j=2( dp=1 )，j=3( dp=2 )，j=4( dp=2 ) 后面。最大 dp 值是2，所以 dp[5] = 2+1 = 3 i=6 ( nums[6]=101 ): 可接在 j=0,1,2,3,4,5 后面，其中 dp[5]=3 最大，所以 dp[6] = 3+1 = 4 i=7 ( nums[7]=18 ): 同样可接在多个位置后， dp[5]=3 最大，所以 dp[7] = 3+1 = 4 最终， dp = [1, 1, 1, 2, 2, 3, 4, 4] ，最大值为 4。 复杂度分析 时间复杂度：O(n²)，因为有双层循环（ i 从 0 到 n-1，对于每个 i ， j 从 0 到 i-1）。 空间复杂度：O(n)，用于存储 dp 数组。 解法二：贪心 + 二分查找（O(n log n)） 这种方法是 更优的解法 ，也是面试中的考察重点。其核心思想是： 让序列上升得尽可能慢 ，这样后面才有更多机会接上更长的序列。 1. 核心思路 我们维护一个数组 tail （或 low ）。 tail[i] 的定义是： 所有长度为 i+1 的上升子序列中，结尾数字最小的那个值 。 为什么记录最小结尾数字？因为对于相同长度的上升子序列，结尾数字越小，将来扩展时能接上更大数字的可能性就越大，潜力就越大。 2. 算法过程 初始化： tail 为空数组。 遍历原数组 nums 中的每个数字 x ： 在 tail 数组中 寻找第一个大于等于 x 的数字的位置 。这可以使用二分查找实现。 如果找到了这个位置（设为 pos ）： 用 x 替换 tail[pos] 。因为 tail[pos] 是长度为 pos+1 的子序列的最小结尾，现在找到了一个更小的结尾 x ，所以更新它。 如果没找到（即 x 大于 tail 中的所有元素）： 将 x 添加到 tail 的末尾。这意味着我们找到了一个更长的上升子序列（长度为当前 tail.length + 1 ），并且其结尾是 x 。 遍历结束后， tail 数组的 长度 就是最长上升子序列的长度。 3. 算法步骤示例 再次以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例： 初始化 tail = [] 处理 10: tail 为空，直接加入。 tail = [10] 处理 9: 在 tail=[10] 中二分查找第一个 ≥9 的元素，是 10 (pos=0)。替换。 tail = [9] （长度为1的子序列，最小结尾从10更新为9） 处理 2: 在 tail=[9] 中二分查找第一个 ≥2 的元素，是 9 (pos=0)。替换。 tail = [2] 处理 5: 在 tail=[2] 中二分查找第一个 ≥5 的元素，没找到（5>2）。添加到末尾。 tail = [2, 5] 处理 3: 在 tail=[2,5] 中二分查找第一个 ≥3 的元素，是 5 (pos=1)。替换。 tail = [2, 3] （长度为2的子序列，最小结尾从5更新为3） 处理 7: 在 tail=[2,3] 中二分查找第一个 ≥7 的元素，没找到（7>3）。添加到末尾。 tail = [2, 3, 7] 处理 101: 在 tail=[2,3,7] 中二分查找第一个 ≥101 的元素，没找到。添加到末尾。 tail = [2, 3, 7, 101] 处理 18: 在 tail=[2,3,7,101] 中二分查找第一个 ≥18 的元素，是 101 (pos=3)。替换。 tail = [2, 3, 7, 18] 遍历结束， tail 的长度为 4，即 LIS 长度为 4。 4. 关键点与理解 tail 数组本身 不一定 是原数组的一个子序列！例如，当 tail 从 [2,5] 变为 [2,3] 时， 3 出现在 5 之后，但在原数组中 3 在 5 之前。 tail 数组只是用来记录“每个长度的最小结尾”，它的长度才是我们想要的结果。 二分查找在这里的作用是 快速定位 当前数字 x 在 tail 数组中的合适位置。查找条件（第一个 ≥ x 的元素）使得算法能够正确维护“最小结尾”的性质。 复杂度分析 时间复杂度：O(n log n)。遍历 n 个元素，每个元素用 O(log n) 时间进行二分查找和可能的替换。 空间复杂度：O(n)，最坏情况下 tail 数组长度等于原数组长度。 总结 最长上升子序列问题有两种经典解法： 动态规划 (O(n²)) ：思路直接，易于理解和实现，适用于小规模数据或作为思路引导。 贪心+二分 (O(n log n)) ：效率更高，是面试中期望回答的最优解。核心在于维护一个“长度-最小结尾”数组，并利用二分查找快速更新它，其最终长度即为答案。你需要理解为什么这个方法可行，并能清晰解释 tail 数组的含义和更新逻辑。