LeetCode 300. 最长递增子序列

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：贪心 + 二分查找
相似题目

题目描述

✅ 300. 最长递增子序列

题目：

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

示例 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) 的算法解决此问题？

思路分析

解法一：动态规划（推荐）

核心思路：

状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度（必须包含 nums[i]）。

状态转移：枚举所有 j < i，若 nums[j] < nums[i]，则 dp[i] = max(dp[j] + 1)。

答案：max(dp[i])（不一定以最后一个元素结尾，需取全局最大值）。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示数组长度。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
                // 至少以自身为结尾，长度为 1
            dp[i] = 1;
            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;
    }
}

func lengthOfLIS(nums []int) int {
	// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
	dp := make([]int, len(nums))
	res := 1
	for i := 0; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			// 如果当前 nums[i] 可以接在 nums[j] 后面
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		// 更新全局最大长度
		res = max(res, dp[i])
	}
	return res
}

解法二：贪心 + 二分查找

核心思路：

维护 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素（贪心：末尾越小，未来越能扩展）。

对每个 nums[i]：若大于 tails 末尾则追加，LIS 长度 +1；否则二分找第一个 ≥ nums[i] 的位置替换，维护最小末尾。

tails 的长度即最终 LIS 长度（注意 tails 本身不一定是实际的 LIS）。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示 tails 数组长度。

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int lo = 0, hi = tails.size();
            // 二分找第一个 >= num 的位置
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails.get(mid) < num) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (lo == tails.size()) {
                // 大于所有末尾，追加
                tails.add(num);
            } else {
                // 替换第一个 >= num 的末尾
                tails.set(lo, num);
            }
        }
        return tails.size();
    }
}

func lengthOfLIS(nums []int) int {
	tails := []int{}
	for _, num := range nums {
		lo, hi := 0, len(tails)
		// 二分找第一个 >= num 的位置
		for lo < hi {
			mid := lo + (hi-lo)/2
			if tails[mid] < num {
				lo = mid + 1
			} else {
				hi = mid
			}
		}
		if lo == len(tails) {
			// 大于所有末尾，追加
			tails = append(tails, num)
		} else {
			// 替换第一个 >= num 的末尾
			tails[lo] = num
		}
	}
	return len(tails)
}

相似题目

题目	难度	考察点
334. 递增的三元子序列	中等	贪心
354. 俄罗斯套娃信封问题	困难	动态规划、二分查找
646. 最长数对链	中等	动态规划、贪心
673. 最长递增子序列的个数	中等	动态规划
1671. 得到山形数组的最少删除次数	困难	动态规划
2370. 最长理想子序列	中等	动态规划
2407. 最长递增子序列 II	困难	动态规划、线段树
1143. 最长公共子序列	中等	动态规划
368. 最大整除子集	中等	动态规划
376. 摆动序列	中等	动态规划、贪心
516. 最长回文子序列	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/87131039