好的，我们这次来详细讲解 LeetCode 第 300 题：「最长递增子序列」（Longest Increasing Subsequence, LIS）。

这是一道非常经典的动态规划问题，也是理解序列型动态规划和贪心+二分查找优化思路的绝佳例题。

1. 题目描述

题目链接：LeetCode 300

难度：中等

题目描述：

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：你能将算法的时间复杂度降低到 O(n log n) 吗？

2. 问题分析与直觉

首先，我们要明确几个关键点：

1. 子序列 vs 子串：子序列不要求连续，只要相对顺序不变即可。这增加了问题的难度，因为我们需要考虑多种组合可能性。
2. 严格递增：意味着序列中的每个元素必须严格大于前一个元素（不能等于）。
3. 目标：我们不需要找出这个具体的子序列是哪些元素，只需求出它的长度。这简化了问题，因为我们只需要记录长度信息。

最直观的暴力解法是枚举所有可能的子序列，并检查它们是否递增。一个长度为 n 的数组有 2^n 个子序列，这种指数级复杂度是完全不可接受的。

我们需要一种更聪明的方法。

3. 循序渐进的第一种解法：动态规划 (O(n²))

动态规划的核心思想是将大问题分解为小问题，并存储小问题的解以避免重复计算。

步骤 1：定义状态（定义 dp 数组）

我们定义 dp[i] 表示：以第 i 个数字（即 nums[i]）为结尾的最长递增子序列的长度。

为什么这么定义？

• 因为对于整个数组的最长递增子序列（LIS），它必然是以数组中某一个元素结尾的。所以，我们只要求出所有 dp[i]，其中的最大值就是整个数组的 LIS 长度。

步骤 2：推导状态转移方程（如何由小问题得出大问题的解）

现在思考：如何求出 dp[i]？

对于位置 i，我们需要考察它之前的所有位置 j (0 <= j < i)：

• 如果 nums[i] > nums[j]：这意味着 nums[i] 可以接在 以 nums[j] 结尾的递增子序列 后面，形成一个更长的递增子序列。
• 此时，以 nums[i] 结尾的 LIS 长度，至少是 dp[j] + 1（+1 就是加上 nums[i] 本身）。

由于 j 可以是 i 之前的所有位置，我们需要找到那个能使得 dp[j] + 1 最大的 j。

因此，状态转移方程为：
dp[i] = max(dp[j]) + 1，对于所有满足 0 <= j < i 且 nums[j] < nums[i] 的 j。

如果不存在这样的 j（即 i 前面的所有数都比 nums[i] 大），那么 nums[i] 自己就构成一个长度为 1 的子序列。所以 dp[i] 的初始值至少为 1。

步骤 3：初始化

每个元素本身至少可以构成一个长度为 1 的递增子序列。因此，我们将整个 dp 数组初始化为 1。
dp = [1] * len(nums)

步骤 4：确定计算顺序

显然，计算 dp[i] 需要用到它前面所有位置的 dp[j] 值。因此，我们使用一个简单的循环，i 从 0 到 n-1，对于每个 i，再用一个内层循环 j 从 0 到 i-1。

步骤 5：得到答案

最终答案不是 dp[n-1]，因为 LIS 不一定以最后一个元素结尾。答案是整个 dp 数组中的最大值，即 max(dp)。

代码实现 (Python)

def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    # 步骤 1 & 3: 定义并初始化 dp 数组
    dp = [1] * n
    # 步骤 4: 确定计算顺序
    for i in range(n):
        for j in range(i):
            # 步骤 2: 状态转移
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    # 步骤 5: 得到答案
    return max(dp)

复杂度分析

• 时间复杂度：O(n²)。外层循环 n 次，内层循环平均 n/2 次。
• 空间复杂度：O(n)。用于存储 dp 数组。

示例演示：以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，手动推导一下 dp 数组：

• i=0: dp[0] = 1 (序列 [10])
• i=1: nums[1]=9，前面没有比它小的数，dp[1] = 1 ([9])
• i=2: nums[2]=2，前面没有比它小的数，dp[2] = 1 ([2])
• i=3: nums[3]=5，前面比它小的有 nums[2]=2，所以 dp[3] = dp[2] + 1 = 2 ([2,5])
• i=4: nums[4]=3，前面比它小的有 nums[2]=2，所以 dp[4] = dp[2] + 1 = 2 ([2,3])
• i=5: nums[5]=7，前面比它小的有 nums[2]=2, nums[3]=5, nums[4]=3。对应的 dp 值为 1, 2, 2。最大值是2，所以 dp[5] = 2 + 1 = 3 ([2,5,7] 或 [2,3,7])
• i=6: nums[6]=101，前面很多比它小的，其中 dp[5]=3 最大，所以 dp[6] = 3 + 1 = 4 ([2,5,7,101] 或 [2,3,7,101])
• i=7: nums[7]=18，前面比它小的数中，dp[5]=3 最大，所以 dp[7] = 3 + 1 = 4 ([2,5,7,18] 或 [2,3,7,18])
• max(dp) = 4，与示例输出一致。

4. 更优的第二种解法：贪心 + 二分查找 (O(n log n))

O(n²) 的解法在 n=2500 时勉强能过，但题目要求我们思考 O(n log n) 的解法。这就需要一种全新的思路。

核心思想

我们维护一个数组 tail（或者叫 lis），这个数组的长度就代表了当前最长递增子序列的长度。tail[i] 的定义非常巧妙：
tail[i] 表示所有长度为 i+1 的递增子序列中，末尾元素最小的那个子序列的末尾元素值。

为什么记录最小的末尾元素？

• 因为对于一个固定的长度，末尾元素越小，意味着这个序列的「增长潜力」越大，后续有更多机会接上更大的数来形成更长的序列。这是一种贪心的思想。

算法步骤

1. 初始化 tail 为空数组。
2. 遍历数组 nums 中的每一个数 num。
3. 对于每个 num：
   • 情况一：如果 num 比 tail 中所有元素都大（即大于 tail 的最后一个元素），说明我们可以将 num 附加到当前最长的子序列后面，从而形成一个更长的子序列。所以我们将 num 添加到 tail 的末尾。
   • 情况二：否则，我们在 tail 数组中寻找第一个大于等于 num 的元素，并用 num 替换它。
     • 这个操作不会改变当前 tail 数组的长度（即当前 LIS 的长度），但它降低了某个长度下的末尾元素的最小值，为后续形成更长的序列创造了更好的条件。

关键点：由于 tail 数组本身是严格递增的（为什么？因为我们要找的是递增子序列，长度更长的序列，其末尾元素必然大于长度更短的序列的末尾元素），所以我们可以使用二分查找来高效地执行步骤 3 中的查找操作。这正是将复杂度降至 O(n log n) 的原因。

代码实现 (Python)

def lengthOfLIS(nums):
    tail = []  # 维护一个潜在的最长递增子序列的「骨架」
    for num in nums:
        # 二分查找：在 tail 中找到第一个大于等于 num 的元素的位置
        left, right = 0, len(tail)
        while left < right:
            mid = (left + right) // 2
            if tail[mid] < num:
                left = mid + 1
            else:
                right = mid
        # 如果 left 等于 tail 的长度，说明 num 比所有元素都大，添加到末尾
        if left == len(tail):
            tail.append(num)
        else:
            # 否则，用 num 替换掉第一个大于等于它的元素，降低这个位置的「门槛」
            tail[left] = num
    # 最终 tail 的长度就是 LIS 的长度
    return len(tail)

复杂度分析

• 时间复杂度：O(n log n)。遍历 n 个元素，对每个元素进行一次二分查找 (O(log n))。
• 空间复杂度：O(n)。最坏情况下 tail 数组需要存储 n 个元素（当输入数组完全递增时）。

示例演示：再次以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，逐步分析 tail 数组的变化：

1. num=10: tail 为空，直接加入 -> tail = [10]
2. num=9: 在 tail 中找到第一个 >=9 的元素是 10，用 9 替换 -> tail = [9] (长度为1的序列，用更小的9做结尾更好)
3. num=2: 找到第一个 >=2 的元素是 9，用 2 替换 -> tail = [2]
4. num=5: 5 > 2，添加到末尾 -> tail = [2, 5]
5. num=3: 找到第一个 >=3 的元素是 5，用 3 替换 -> tail = [2, 3] (现在长度为2的序列结尾是3，比5更优)
6. num=7: 7 > 3，添加到末尾 -> tail = [2, 3, 7]
7. num=101: 101 > 7，添加到末尾 -> tail = [2, 3, 7, 101]
8. num=18: 找到第一个 >=18 的元素是 101，用 18 替换 -> tail = [2, 3, 7, 18]
   最终 tail 的长度为 4，即 LIS 长度。

注意：tail 数组存储的并不一定是真实的最长递增子序列（比如最后是 [2,3,7,18] 而不是 [2,3,7,101]），但它的长度一定是正确的。我们的目标是长度，所以这完全可行。

5. 总结与对比

对于这道题，掌握 O(n log n) 的解法是很有价值的，因为它体现了通过改变状态定义和利用数据结构（二分查找） 来优化动态规划问题的经典技巧。

希望这个从基础动态规划到高级优化的循序渐进讲解，能帮助你彻底理解「最长递增子序列」这道题！