好的，我们这次来详细讲解 LeetCode 第 300 题「最长递增子序列」。

1. 题目描述

给你一个整数数组 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
解释：最长递增子序列是 [0,1,2,3]，长度为 4。

示例 3：

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

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

2. 题意理解

• 子序列 ≠ 子数组（不要求连续）
• 严格递增：nums[i] < nums[i+1]，不能相等
• 我们要找的是最长的那个递增子序列的长度（LIS, Longest Increasing Subsequence）

3. 思路演进

3.1 暴力法（不可行）

枚举所有子序列，检查是否递增，并记录最长长度。
子序列个数为 2^n，n 最多 2500，不可行。

3.2 动态规划（O(n²)）

定义状态：
dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

状态转移：
对于每个 i，我们看前面所有 j < i：

• 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 结尾的递增子序列后面，形成更长的子序列。
• 所以 dp[i] = max(dp[i], dp[j] + 1) 对所有满足 nums[j] < nums[i] 的 j。

初始条件：
每个位置单独作为一个子序列，长度至少为 1，所以 dp[i] = 1。

结果：
max(dp[0..n-1])。

例子：nums = [10, 9, 2, 5, 3, 7, 101, 18]

• i=0: dp[0]=1
• i=1: nums[1]=9，前面 10>9，不能接，dp[1]=1
• i=2: nums[2]=2，前面都大于 2，dp[2]=1
• i=3: nums[3]=5，前面 2<5，可接在 i=2 后，dp[3]=dp[2]+1=2
• i=4: nums[4]=3，前面 2<3，可接在 i=2 后，dp[4]=dp[2]+1=2
• i=5: nums[5]=7，前面 2,5,3 都小于 7：
  • 接在 i=2 后：长度 2
  • 接在 i=3 后：长度 3
  • 接在 i=4 后：长度 3
  • 取最大：dp[5]=3
• i=6: nums[6]=101，前面都小于 101，找前面最大的 dp 值加 1，dp[6]=4
• i=7: nums[7]=18，前面小于 18 的最大 dp 值是 dp[5]=3，所以 dp[7]=4

最终 max(dp) = 4。

时间复杂度：O(n²)
空间复杂度：O(n)

3.3 贪心 + 二分查找（O(n log n)）

我们希望 LIS 增长得尽可能慢，这样后面更容易接上更大的数。

维护一个数组 tail：
tail[i] 表示长度为 i+1 的递增子序列的最小末尾值。

算法步骤：

1. 初始化 tail = []
2. 遍历每个数 x：
   • 如果 x 大于 tail 的最后一个元素，则直接加入 tail（表示最长长度增加 1）
   • 否则，在 tail 中二分查找第一个大于等于 x 的位置，用 x 替换它（这样该位置对应的长度序列的末尾值变小，后面更容易接上更大的数）

最终结果：len(tail)

例子：nums = [10, 9, 2, 5, 3, 7, 101, 18]

• x=10: tail = [10]
• x=9: 9<10，替换 10 → tail = [9]
• x=2: 2<9，替换 9 → tail = [2]
• x=5: 5>2，加入 → tail = [2,5]
• x=3: 3<5，在 tail 中找到 5（第一个 ≥3），替换 → tail = [2,3]
• x=7: 7>3，加入 → tail = [2,3,7]
• x=101: 加入 → tail = [2,3,7,101]
• x=18: 18<101，在 tail 中找到 101（第一个 ≥18），替换 → tail = [2,3,7,18]

长度 = 4。

注意：tail 不是真正的 LIS，但长度等于 LIS 的长度。

时间复杂度：O(n log n)
空间复杂度：O(n)

4. 代码实现

4.1 动态规划版本

def lengthOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

4.2 贪心 + 二分查找版本

def lengthOfLIS(nums):
    tail = []
    for x in nums:
        # 二分查找插入位置
        left, right = 0, len(tail)
        while left < right:
            mid = (left + right) // 2
            if tail[mid] < x:
                left = mid + 1
            else:
                right = mid
        # 如果 x 大于所有 tail 中的元素，left 会等于 len(tail)
        if left == len(tail):
            tail.append(x)
        else:
            tail[left] = x
    return len(tail)

5. 总结

• O(n²) DP：直观，适合理解问题本质
• O(n log n) 贪心+二分：高效，适合大数据量
• 关键思想：让递增序列的末尾尽可能小，以便后续扩展

这样讲解是否清晰？我们可以继续深入某个细节，或者换下一题。