最长递增子序列（LIS）问题

字数 2283 2025-11-08 10:03:34

最长递增子序列（LIS）问题

最长递增子序列（Longest Increasing Subsequence, LIS）问题是计算机科学中的一个经典问题。给定一个整数序列，我们需要找到其中最长的（不一定连续）子序列，使得这个子序列中的元素是严格递增的。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，最长的递增子序列之一是 [2, 5, 7, 101]，其长度为4。

解决LIS问题有两种主流方法：动态规划（时间复杂度O(n²)）和贪心结合二分查找（时间复杂度O(n log n)）。我们将重点讲解更高效的后一种方法。

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

这种方法的核心思想是：我们试图让递增序列增长得尽可能“慢”，以便有更大的潜力容纳后续更多的数字。我们维护一个数组 tail（或常命名为 dp），其中 tail[i] 表示所有长度为 i+1 的递增子序列中，最小的末尾元素值。

详细步骤：

初始化：
- 创建一个空数组 tail，用于存储潜在的子序列末尾值。
- 将给定序列 nums 的第一个数字放入 tail。此时，tail = [nums[0]]。这表示目前我们找到了一个长度为1的递增子序列，其末尾的最小值是 nums[0]。
遍历序列：
- 从第二个元素开始，依次处理序列 nums 中的每一个数字，我们称当前处理的数字为 x。
比较与放置策略：
- 将 x 与 tail 数组中的最后一个元素（即当前最长子序列的末尾）进行比较。
- 情况一：如果 x 大于 tail 的最后一个元素。
  - 这说明 x 可以接在当前最长的递增子序列之后，形成一个更长的子序列。
  - 操作：将 x 直接添加到 tail 数组的末尾。
  - 示例：假设 tail = [2, 5]（表示长度为1的子序列末尾最小是2，长度为2的子序列末尾最小是5），现在 x = 7。因为 7 > 5，所以我们将7加入，得到 tail = [2, 5, 7]。这意味着我们找到了一个长度为3的递增子序列 [2, 5, 7]。
- 情况二：如果 x 小于或等于 tail 的最后一个元素。
  - 这说明 x 无法扩展当前最长的子序列。但是，它有可能作为一个更小的末尾值，去更新一个更短长度的子序列，使得那个长度的子序列的“潜力”更大（即末尾值更小）。
  - 操作：在 tail 数组中找到第一个大于或等于 x 的元素，并用 x 替换它。这个查找过程使用二分查找来完成，以保证效率。
  - 示例：假设 tail = [2, 5, 7]，现在 x = 3。
    - 3 不大于 7，所以我们不能扩展长度。
    - 我们在 tail 中寻找第一个大于等于 3 的数，找到的是 5（在索引1的位置）。
    - 我们用 3 替换 tail[1]（即5）。现在 tail = [2, 3, 7]。
  - 这个操作的意义是什么？ 我们并没有改变当前最长子序列的长度（仍然是3），但我们让长度为2的子序列的末尾值从5降为了3。这意味着，以后只要有一个大于3但小于7的数（比如4），它现在就可以接在 [2, 3] 后面形成一个长度为3的子序列 [2, 3, 4]，这比之前必须大于5的条件要宽松。这体现了“让序列增长得更慢，潜力更大”的贪心思想。
得到结果：
- 在遍历完整个 nums 序列后，tail 数组的长度就是最长递增子序列的长度。
- 重要提示：tail 数组本身并不一定是一个真实存在于 nums 中的最长递增子序列，但它正确地记录了最长递增子序列的长度。

完整示例演示：

以序列 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例。

初始化：tail = [10] (长度len=1)
处理 x=9：
- 9 < 10，在 tail 中找第一个>=9的数，是10（索引0）。
- 替换：tail = [9] (len=1)
处理 x=2：
- 2 < 9，在 tail 中找第一个>=2的数，是9（索引0）。
- 替换：tail = [2] (len=1)
处理 x=5：
- 5 > 2，添加到末尾：tail = [2, 5] (len=2)
处理 x=3：
- 3 < 5，在 tail 中找第一个>=3的数，是5（索引1）。
- 替换：tail = [2, 3] (len=2)
处理 x=7：
- 7 > 3，添加到末尾：tail = [2, 3, 7] (len=3)
处理 x=101：
- 101 > 7，添加到末尾：tail = [2, 3, 7, 101] (len=4)
处理 x=18：
- 18 < 101，在 tail 中找第一个>=18的数，是101（索引3）。
- 替换：tail = [2, 3, 7, 18] (len=4)

遍历结束，最长递增子序列的长度为4。虽然最终的 tail 数组是 [2, 3, 7, 18]，但原序列中一个有效的LIS是 [2, 5, 7, 101] 或 [2, 3, 7, 101]。算法成功计算出了长度。

总结：
这种方法通过维护一个“潜力最大”的末尾值数组，并利用二分查找进行高效更新，将时间复杂度从O(n²)优化到了O(n log n)，是解决LIS问题的优选算法。

最长递增子序列（LIS）问题最长递增子序列（Longest Increasing Subsequence, LIS）问题是计算机科学中的一个经典问题。给定一个整数序列，我们需要找到其中最长的（不一定连续）子序列，使得这个子序列中的元素是严格递增的。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18] ，最长的递增子序列之一是 [2, 5, 7, 101] ，其长度为4。解决LIS问题有两种主流方法：动态规划（时间复杂度O(n²)）和贪心结合二分查找（时间复杂度O(n log n)）。我们将重点讲解更高效的后一种方法。方法二：贪心策略 + 二分查找（O(n log n)）这种方法的核心思想是：我们试图让递增序列增长得尽可能“慢”，以便有更大的潜力容纳后续更多的数字。我们维护一个数组 tail （或常命名为 dp ），其中 tail[i] 表示所有长度为 i+1 的递增子序列中，最小的末尾元素值。详细步骤：初始化：创建一个空数组 tail ，用于存储潜在的子序列末尾值。将给定序列 nums 的第一个数字放入 tail 。此时， tail = [nums[0]] 。这表示目前我们找到了一个长度为1的递增子序列，其末尾的最小值是 nums[0] 。遍历序列：从第二个元素开始，依次处理序列 nums 中的每一个数字，我们称当前处理的数字为 x 。比较与放置策略：将 x 与 tail 数组中的最后一个元素（即当前最长子序列的末尾）进行比较。情况一：如果 x 大于 tail 的最后一个元素。这说明 x 可以接在当前最长的递增子序列之后，形成一个更长的子序列。操作：将 x 直接添加到 tail 数组的末尾。示例：假设 tail = [2, 5] （表示长度为1的子序列末尾最小是2，长度为2的子序列末尾最小是5），现在 x = 7 。因为 7 > 5 ，所以我们将7加入，得到 tail = [2, 5, 7] 。这意味着我们找到了一个长度为3的递增子序列 [2, 5, 7] 。情况二：如果 x 小于或等于 tail 的最后一个元素。这说明 x 无法扩展当前最长的子序列。但是，它有可能作为一个更小的末尾值，去更新一个更短长度的子序列，使得那个长度的子序列的“潜力”更大（即末尾值更小）。操作：在 tail 数组中找到第一个大于或等于 x 的元素，并用 x 替换它。这个查找过程使用二分查找来完成，以保证效率。示例：假设 tail = [2, 5, 7] ，现在 x = 3 。 3 不大于 7 ，所以我们不能扩展长度。我们在 tail 中寻找第一个大于等于 3 的数，找到的是 5 （在索引1的位置）。我们用 3 替换 tail[1] （即5）。现在 tail = [2, 3, 7] 。这个操作的意义是什么？我们并没有改变当前最长子序列的长度（仍然是3），但我们让长度为2的子序列的末尾值从5降为了3。这意味着，以后只要有一个大于3但小于7的数（比如4），它现在就可以接在 [2, 3] 后面形成一个长度为3的子序列 [2, 3, 4] ，这比之前必须大于5的条件要宽松。这体现了“让序列增长得更慢，潜力更大”的贪心思想。得到结果：在遍历完整个 nums 序列后， tail 数组的长度就是最长递增子序列的长度。重要提示： tail 数组本身并不一定是一个真实存在于 nums 中的最长递增子序列，但它正确地记录了最长递增子序列的长度。完整示例演示：以序列 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例。初始化： tail = [10] (长度len=1) 处理 x=9 ： 9 < 10，在 tail 中找第一个>=9的数，是10（索引0）。替换： tail = [9] (len=1) 处理 x=2 ： 2 < 9，在 tail 中找第一个>=2的数，是9（索引0）。替换： tail = [2] (len=1) 处理 x=5 ： 5 > 2，添加到末尾： tail = [2, 5] (len=2) 处理 x=3 ： 3 < 5，在 tail 中找第一个>=3的数，是5（索引1）。替换： tail = [2, 3] (len=2) 处理 x=7 ： 7 > 3，添加到末尾： tail = [2, 3, 7] (len=3) 处理 x=101 ： 101 > 7，添加到末尾： tail = [2, 3, 7, 101] (len=4) 处理 x=18 ： 18 < 101，在 tail 中找第一个>=18的数，是101（索引3）。替换： tail = [2, 3, 7, 18] (len=4) 遍历结束，最长递增子序列的长度为4。虽然最终的 tail 数组是 [2, 3, 7, 18] ，但原序列中一个有效的LIS是 [2, 5, 7, 101] 或 [2, 3, 7, 101] 。算法成功计算出了长度。总结：这种方法通过维护一个“潜力最大”的末尾值数组，并利用二分查找进行高效更新，将时间复杂度从O(n²)优化到了O(n log n)，是解决LIS问题的优选算法。