最长递增子序列（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)）。下面详细讲解更高效的贪心+二分查找方法。

步骤 1：理解贪心策略

贪心策略的核心是维护一个数组 tail，其中 tail[i] 表示长度为 i+1 的所有递增子序列中末尾元素的最小值。通过不断更新 tail，保证其始终是单调递增的，从而可以使用二分查找优化插入过程。

步骤 2：算法流程

1. 初始化：创建空数组 tail，用于存储不同长度递增子序列的最小末尾值。
2. 遍历原序列：对于每个数字 num：
   • 如果 num 大于 tail 的最后一个元素（即可以扩展最长子序列），则直接追加到 tail 末尾。
   • 否则，在 tail 中找到第一个大于等于 num 的位置，用 num 替换该位置的值（目的是让后续扩展更灵活）。
3. 结果：最终 tail 的长度即为 LIS 的长度。

步骤 3：具体示例

以序列 [3, 5, 2, 8, 10, 7, 9] 为例：

• 初始 tail = []
• num=3：tail 为空，直接加入 → tail = [3]
• num=5：大于 tail 末尾的 3，追加 → tail = [3, 5]
• num=2：小于 5，二分查找找到第一个 ≥2 的位置（索引 0），替换 → tail = [2, 5]
• num=8：大于 5，追加 → tail = [2, 5, 8]
• num=10：大于 8，追加 → tail = [2, 5, 8, 10]
• num=7：小于 10，二分查找替换 8 → tail = [2, 5, 7, 10]
• num=9：小于 10，二分查找替换 10 → tail = [2, 5, 7, 9]

最终 LIS 长度为 4（注意 tail 不一定是最优子序列本身，但长度正确）。

步骤 4：二分查找的实现

在 tail 中查找第一个大于等于 num 的位置（左边界二分）：

def bisect_left(tail, target):
    left, right = 0, len(tail) - 1
    while left <= right:
        mid = (left + right) // 2
        if tail[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left  # 返回插入位置

步骤 5：完整代码（Python）

def length_of_lis(nums):
    tail = []
    for num in nums:
        # 二分查找插入位置
        left, right = 0, len(tail)
        while left < right:
            mid = (left + right) // 2
            if tail[mid] < num:
                left = mid + 1
            else:
                right = mid
        # 如果 left 等于 tail 长度，说明需要扩展
        if left == len(tail):
            tail.append(num)
        else:
            tail[left] = num
    return len(tail)

步骤 6：复杂度分析

• 时间复杂度：O(n log n)，每个元素最多进行一次二分查找。
• 空间复杂度：O(n)，tail 数组的长度最多为 n。

总结
贪心+二分法通过维护最小末尾值数组，将问题转化为单调序列的维护，巧妙降低了时间复杂度。实际面试中可能还会要求输出具体的 LIS 序列（需额外记录路径），但核心逻辑基于上述方法。