300. 最长递增子序列#

在算法面试中,最长递增子序列(Longest Increasing Subsequence, LIS)是一道经典的动态规划题目。这篇文章将通过具体的例子,带你一步步理解这个问题的解决思路。

🎯 问题描述#

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

注意:子序列不要求连续,但要保持原始顺序。

例如:

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

问题描述#

题目目标#

给定一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除若干元素或不删除元素但不改变其余元素顺序。

示例 1#

输入： nums = [10,9,2,5,3,7,101,18] 输出： 4 说明： 最长递增子序列之一为 [2,3,7,101]

💡 从具体例子开始理解#

让我们通过一个更简单的例子来逐步理解这个问题:

nums = [3,1,4,5,2]

如果我们要手动找出这个数组的最长递增子序列,我们会怎么思考?

1. 从第一个数字 3 开始:

   • [3] 是一个长度为1的递增子序列
   • 后面比3大的数有: 4,5,所以可以得到 [3,4,5]

2. 从第二个数字 1 开始:

   • [1] 是一个长度为1的递增子序列
   • 后面比1大的数有: 4,5,2
   • 可以得到 [1,4,5] 或 [1,2]

3. 从第三个数字 4 开始:

   • [4] 是一个长度为1的递增子序列
   • 后面比4大的只有5,所以可以得到 [4,5]

… 以此类推

通过这个例子,我们发现一个关键点:对于每个位置i,我们需要知道以nums[i]结尾的最长递增子序列的长度。

🔍 发现状态定义#

这个发现直接引导我们找到了动态规划的状态定义:

dp[i] 表示: 以 nums[i] 结尾的最长递增子序列的长度。

让我们通过例子来理解这个状态定义:

nums = [3,1,4,5,2]
初始化: dp[i] = 1 (因为每个数字本身就是长度为1的子序列)
dp = [1,1,1,1,1]

🎨 推导状态转移方程#

关键问题是:如何计算dp[i]?

还是用具体例子来思考: 当我们要计算dp3时:

1. 看前面所有比5小的数字:
   • 3 < 5, 可以接在3后面,此时长度为dp[0] + 1 = 2
   • 1 < 5, 可以接在1后面,此时长度为dp[1] + 1 = 2
   • 4 < 5, 可以接在4后面,此时长度为dp[2] + 1 = 2

所以dp[3] = max(dp[j] + 1),其中j < i且nums[j] < nums[i]

完整的状态转移过程:

nums = [3,1,4,5,2]
dp[0] = 1                     dp = [1,1,1,1,1]
dp[1] = 1                     dp = [1,1,1,1,1]
dp[2] = max(dp[1]+1) = 2     dp = [1,1,2,1,1]
dp[3] = max(dp[2]+1) = 3     dp = [1,1,2,3,1]
dp[4] = max(dp[1]+1) = 2     dp = [1,1,2,3,2]

📝 代码实现#

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 边界情况：空数组或 null 数组的 LIS 长度定义为 0
        if (nums == null || nums.length == 0) return 0;

        // dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // 初始化:每个数字本身就是长度为1的子序列
        Arrays.fill(dp, 1);

        // maxLen 记录全局范围内的最长递增子序列长度
        int maxLen = 1;

        // 外层循环：依次计算每个位置 i 的 dp[i]
        for (int i = 1; i < nums.length; i++) {
            // 内层循环：枚举 i 之前的每个位置 j，尝试把 nums[i] 接在其后
            for (int j = 0; j < i; j++) {
                // 如果当前数字大于之前的数字,可以接在该数字后面形成更长的递增子序列
                if (nums[i] > nums[j]) {
                    // 状态转移：dp[i] = max(dp[i], dp[j] + 1)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 每次算完 dp[i] 后，及时更新全局最优答案
            maxLen = Math.max(maxLen, dp[i]);
        }

        // 返回整个数组的最长递增子序列长度
        return maxLen;
    }
}

🎯 复杂度分析#

• 时间复杂度: O(n²),其中n是数组长度
• 空间复杂度: O(n),用于存储dp数组

💡 进阶思考#

这个O(n²)的解法是最优解吗?

实际上,我们可以用二分查找将时间复杂度优化到O(nlogn)。具体思路是维护一个递增数组,表示到目前为止找到的最长递增子序列。这个优化留给读者思考,我们将在下一篇文章中详细讨论。

🎓 面试指南#

遇到这类问题时,建议按以下步骤思考:

1. 从小规模例子开始,手动模拟找出递增子序列
2. 思考对于每个位置,我们需要知道什么信息
3. 将这个信息转化为状态定义
4. 通过具体例子推导状态转移方程
5. 考虑边界情况和初始化
6. 最后考虑优化空间

记住,动态规划的难点往往在于找到正确的状态定义。通过具体例子来思考,往往能帮助我们更直观地理解问题。

希望这篇文章能帮助你深入理解最长递增子序列问题。如果你有任何问题,欢迎在评论区讨论！