Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 300: 最长递增子序列 - 动态规划与贪心优化

Posted on Edited on In , ,
Symbols count in article: 4.2k Reading time ≈ 4 mins.
详细解析 LeetCode 300 '最长递增子序列' 问题的动态规划解法和更优的贪心算法结合二分查找的思路，并提供带有注释的 Go 语言实现。

问题描述

给定一个整数数组 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

解题思路

方法一：动态规划 (Dynamic Programming)

这是解决 LIS (Longest Increasing Subsequence) 问题的经典方法。

核心思想：

我们定义 dp[i] 为以 nums[i] 这个数结尾的最长递增子序列的长度。
为了计算 dp[i]，我们需要遍历 i 之前的所所有元素 nums[j] (其中 0 <= j < i)：

  • 如果 nums[i] > nums[j]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列之后，形成一个更长的递增子序列。此时，这个新的递增子序列的长度就是 dp[j] + 1。
  • 如果 nums[i] <= nums[j]，则 nums[i] 不能接在 nums[j] 之后形成严格递增子序列。

因此，dp[i] 的值应该是所有满足 nums[i] > nums[j] 的 dp[j] + 1 中的最大值。如果没有任何 j 满足条件（例如 nums[i] 是当前所有数字中最小的），那么 dp[i] 就是 1（即 nums[i] 自身构成一个子序列）。

状态转移方程：

dp[i] = max(dp[j]) + 1，其中 0 ≤ j < i 且 nums[i] > nums[j]。
如果不存在这样的 j，则 dp[i] = 1。

初始化：

dp 数组中所有元素的初始值都为 1，因为每个元素本身至少可以构成一个长度为 1 的递增子序列。

最终结果：

遍历整个 dp 数组，其中的最大值即为整个数组的最长递增子序列的长度。因为 LIS 可能以任何元素结尾。

代码实现 (Go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package main

// max 返回两个整数中的较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// lengthOfLIS 使用动态规划计算最长递增子序列的长度
func lengthOfLIS_dp(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	n := len(nums)
	// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
	dp := make([]int, n)

	// 初始化 dp 数组，每个元素自身构成长度为 1 的递增子序列
	for i := 0; i < n; i++ {
		dp[i] = 1
	}

	// 填充 dp 数组
	// i 从第 1 个元素开始（索引 0 已经初始化为 1）
	for i := 0; i < n; i++ {
		// 遍历 i 之前的所有元素 j
		for j := 0; j < i; j++ {
			// 如果 nums[i] 大于 nums[j]，说明 nums[i] 可以接在 nums[j] 后面
			if nums[i] > nums[j] {
				// 更新 dp[i]，取当前 dp[i] 和 dp[j]+1 中的较大值
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
	}

	// 找到 dp 数组中的最大值，即为整个序列的 LIS 长度
	maxLength := 0
	for i := 0; i < n; i++ {
		maxLength = max(maxLength, dp[i])
	}

	return maxLength
}

复杂度分析

  • 时间复杂度： O(n^2)。我们有两个嵌套循环，外层循环 n 次，内层循环平均 n/2 次。
  • 空间复杂度： O(n)。需要一个 dp 数组来存储中间状态。

方法二：贪心 + 二分查找

这种方法更为高效，可以将时间复杂度优化到 O(n log n)。

核心思想：

我们维护一个数组 tails（或者叫 min_end_elements_of_lis_with_length_k），其中 tails[k] 存储的是所有长度为 k+1 的递增子序列中，末尾元素的最小值。这个 tails 数组一定是严格递增的。

证明 tails 数组的单调性：
假设 tails[k] (长度为 k+1 的 LIS 的最小末尾) >= tails[k+1] (长度为 k+2 的 LIS 的最小末尾)。
这意味着存在一个长度为 k+2 的 LIS，其末尾元素 tails[k+1] 小于等于 长度为 k+1 的 LIS 的最小末尾元素 tails[k]。
那么这个长度为 k+2 的 LIS 的前 k+1 个元素构成的子序列，其末尾元素一定小于 tails[k+1]，也就小于等于 tails[k]。这与 tails[k] 是长度为 k+1 的 LIS 的最小末尾元素矛盾。
所以 tails 数组必须是严格递增的。

算法步骤：

  1. 初始化一个空数组 tails。这个数组将用来存储我们构建的最长递增子序列（或者更准确地说，是各长度递增子序列的最小末尾元素）。

  2. 遍历输入数组 nums 中的每个元素 num：

    • 情况 1： 如果 num 大于 tails 数组中的所有元素（即 num > tails[len(tails)-1]，如果 tails 非空），或者 tails 为空，那么 num 可以扩展当前最长的递增子序列。我们将 num 添加到 tails 的末尾。这表示我们找到了一个更长的递增子序列。
    • 情况 2： 如果 num 不大于 tails 中的所有元素，这意味着 num 不能直接扩展当前已知的最长递增子序列。但是，num 可能可以替换 tails 数组中某个元素，形成一个长度相同但末尾元素更小的递增子序列。
      我们使用二分查找，在 tails 数组中找到第一个大于或等于 num 的元素 tails[j]，然后用 num 替换 tails[j]。
      这样做的意义是：我们发现了一个可以构成长度为 j+1 的递增子序列，并且其末尾元素是 num（比原来的 tails[j] 更小或相等）。这为后续元素提供了更多可能性（因为末尾元素越小，越容易接上新元素）。

  3. 遍历完成后，tails 数组的长度就是整个序列的最长递增子序列的长度。

为什么这种方法有效？
tails 数组的长度 len 始终代表当前已发现的 LIS 的长度。
当我们用 num 替换 tails[j] 时，我们并没有改变 LIS 的长度，而是优化了构成长度为 j+1 的 LIS 的条件（使其末尾元素更小）。如果 num 大于 tails 的所有元素，我们就增加 LIS 的长度。
这个过程保证了 tails 数组始终存储着在当前遍历进度下，构建不同长度递增子序列的"最优"（即末尾元素最小）选择。

代码实现 (Go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package main

// lengthOfLIS 使用贪心 + 二分查找计算最长递增子序列的长度
func lengthOfLIS_greedy_binary_search(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	// tails[i] 表示长度为 i+1 的所有递增子序列中，末尾元素的最小值
	tails := []int{}

	for _, num := range nums {
		// 如果 tails 为空，或者 num 大于 tails 中最后一个元素
		// 则 num 可以扩展当前最长的递增子序列
		if len(tails) == 0 || num > tails[len(tails)-1] {
			tails = append(tails, num)
		} else {
			// 否则，在 tails 数组中找到第一个大于或等于 num 的元素，并替换它
			// 这意味着我们找到了一个长度相同的递增子序列，但其末尾元素更小
			
			// 二分查找：在 tails 数组中找到 num 的插入位置
			// 目的是找到最小的 j 使得 tails[j] >= num
			left, right := 0, len(tails)-1
			pos := right // 如果 num 比 tails 所有元素都小，则替换 tails[0]
			
			for left <= right {
				mid := left + (right-left)/2
				if tails[mid] >= num {
					pos = mid // 找到了一个可能的替换位置
					right = mid - 1 // 尝试在左半部分找更小的索引
				} else {
					left = mid + 1 // num 较大，需要在右半部分找
				}
			}
			tails[pos] = num
		}
	}
	// tails 数组的长度即为最长递增子序列的长度
	return len(tails)
}

复杂度分析

  • 时间复杂度： O(n log n)。外层循环遍历 nums 数组需要 n 次，内层二分查找操作需要 log k 次，其中 k 是 tails 数组的当前长度（k <= n）。
  • 空间复杂度： O(n)。最坏情况下，tails 数组可能存储所有 n 个元素（例如当 nums 本身就是严格递增的时候）。

方法比较

方面 动态规划 (DP) 贪心 + 二分查找
时间复杂度 O(n^2) O(n log n)
空间复杂度 O(n) O(n)
实现难度 相对简单，易于理解 稍复杂，需要理解贪心思想和二分查找的应用
优点 思路直接 效率更高
缺点 效率较低，大数据量下可能超时 理解起来不如DP直观
推荐度 ★★★☆☆ ★★★★★

关键收获

  • 动态规划是解决 LIS 问题的基础方法，理解 dp[i] 的定义（以 nums[i] 结尾的 LIS 长度）是关键。
  • 贪心 + 二分查找 提供了一种更优的解决方案。核心在于维护 tails 数组，它存储了不同长度递增子序列的最小末尾元素。这种策略确保我们总是在为未来留下最好的可能性。
  • 对于子序列问题，动态规划是一个常见的思考方向。当 DP 出现平方复杂度时，可以考虑是否有贪心策略或者数据结构（如二分查找、树状数组、线段树）可以优化。

这道题是理解动态规划和序列问题优化的一个很好的例子。两种方法都值得掌握。