最长递增子序列（Longest Increasing Subsequence）

问题简介

🔗 LeetCode 300. 最长递增子序列

题解github地址: https://github.com/swf2020/LeetCode-Hot100-Solutions

题目描述

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

• 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
• 严格递增 指的是对于子序列中任意相邻两个元素 a[i] < a[i+1]。

---

示例说明

示例 1：

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

示例 2：

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

示例 3：

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

---

解题思路

✅ 方法一：动态规划（DP）—— O(n²)

思路步骤：

1. 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 初始时，每个 dp[i] = 1（每个元素自身构成长度为1的子序列）。
3. 对于每个 i，遍历所有 j < i：
   • 如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的子序列后，即 dp[i] = max(dp[i], dp[j] + 1)。
4. 最终答案是 max(dp[0...n-1])。

💡 时间复杂度较高，但逻辑清晰，适合理解 LIS 本质。

---

✅ 方法二：贪心 + 二分查找 —— O(n log n)

思路步骤：

1. 维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。
2. 遍历 nums 中每个元素 x：
   • 如果 x 大于 tails 的最后一个元素，则直接追加（说明可以延长当前最长子序列）。
   • 否则，在 tails 中使用二分查找找到第一个 ≥ x 的位置，并用 x 替换它（保持 tails 的性质）。
3. tails 的长度即为 LIS 的长度。

💡 关键点：tails 数组本身不一定是真实的 LIS，但它能正确维护 LIS 的长度。

---

代码实现

// 方法一：动态规划 O(n²)
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

// 方法二：贪心 + 二分 O(n log n)
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails.get(mid) < x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (left == tails.size()) {
                tails.add(x);
            } else {
                tails.set(left, x);
            }
        }
        return tails.size();
    }
}

// 方法一：动态规划 O(n²)
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    res := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        res = max(res, dp[i])
    }
    return res
}

// 方法二：贪心 + 二分 O(n log n)
func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        // 二分查找第一个 >= x 的位置
        left, right := 0, len(tails)
        for left < right {
            mid := (left + right) / 2
            if tails[mid] < x {
                left = mid + 1
            } else {
                right = mid
            }
        }
        if left == len(tails) {
            tails = append(tails, x)
        } else {
            tails[left] = x
        }
    }
    return len(tails)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

---

示例演示

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

方法一 DP 过程：

i	nums[i]	dp[i] 计算过程	dp[i]
0	10	初始	1
1	9	无更小	1
2	2	无更小	1
3	5	2<5 → dp[3]=dp[2]+1=2	2
4	3	2<3 → dp[4]=2	2
5	7	2,5,3<7 → max(1+1,2+1,2+1)=3	3
6	101	… → 4	4
7	18	… → 4	4

✅ 最终结果：4

方法二 tails 过程：

x	tails（变化）
10	[10]
9	[9]
2	[2]
5	[2,5]
3	[2,3]
7	[2,3,7]
101	[2,3,7,101]
18	[2,3,7,18]

✅ 最终长度：4

---

答案有效性证明

方法一（DP）：

• 正确性：dp[i] 明确定义为以 i 结尾的 LIS 长度，通过枚举所有可能前驱 j，确保状态转移完整。
• 最优子结构：LIS 具有最优子结构性质，局部最优可推导全局最优。

方法二（贪心 + 二分）：

• 关键引理：tails 数组始终保持严格递增（可用反证法证明）。
• 替换策略：用更小的值替换 tails 中的元素，不会影响已有的 LIS 长度，但为后续扩展提供更大可能性。
• 长度不变性：每次只修改 tails 中某个位置的值，或在末尾追加，因此 len(tails) 始终等于当前 LIS 长度。

📌 虽然 tails 不一定是真实子序列，但其长度等于 LIS 长度，这是该算法的核心洞察。

---

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
动态规划	O(n²)	O(n)	n ≤ 10⁴
贪心 + 二分	O(n log n)	O(n)	n ≤ 10⁵ 或更高

💡 在 LeetCode 测试用例中，两种方法均可通过，但 O(n log n) 更优。

---

问题总结

• 核心思想：LIS 是经典动态规划问题，但可通过贪心策略 + 二分优化提升效率。
• 关键技巧：
  • DP 状态定义要清晰（以 i 结尾）。
  • 贪心法中维护“最小末尾”数组 tails 是突破口。
• 扩展思考：
  • 如何输出具体的 LIS 序列？（需记录路径，DP 可行，贪心法较难）
  • 若允许非严格递增（≤），如何修改？（二分查找条件改为 <=）

✅ 掌握这两种解法，不仅能解决本题，也为处理其他子序列类问题（如 LC 354 俄罗斯套娃信封）打下基础。