112.最长递增子序列
题目
给你一个整数数组 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
思路
动态规划
最通俗的想法： 我们站在每个数字的位置上问一句话
如果这个数字作为递增子序列的最后一个数字，最长能有多长？
定义： dp[i] 是 以 nums[i]结尾的最长递增子序列长度
比如： nums = [10,9,2,5,3,7,101,18] 中当 nums[i] = 7，我们就去看它前面的数字:
[10, 9, 2, 5, 3]
只有比7小的数字，才能接在7前面，比如:
2 -> 7
5 -> 7
3 -> 7
所以我们要从前面那些比它小的数字里，找一个最长的，然后接上当前这个数字。
公式就是:
如果 nums[j] < nums[i]
dp[i] = max(dp[i], dp[j] + 1)
意思是：前面某个递增序列 + 当前nums[i]
举个小例子
数组：
[10, 9, 2, 5, 3, 7]
一开始，每个数字自己都能成为长度为 1 的递增子序列：
dp = [1, 1, 1, 1, 1, 1]
看到 5：
前面比 5 小的是 2
所以 2 -> 5
dp[5的位置] = 2
看到 7：
前面比 7 小的是 2、5、3
2 -> 7 长度 2
2 -> 5 -> 7 长度 3
2 -> 3 -> 7 长度 3
所以 dp[7的位置] = 3
最后答案就是 dp 里面最大的那个值。
class Solution {
fun lengthOfLIS(nums: IntArray): Int {
// 如果数组为空，最长长度就是 0
if (nums.isEmpty()) return 0
// dp[i] 表示：
// 以 nums[i] 作为最后一个数字时，
// 最长递增子序列的长度
val dp = IntArray(nums.size) { 1 }
// 最终答案
var ans = 1
// i 表示当前正在看的数字
for (i in nums.indices) {
// j 表示 i 前面的数字
for (j in 0 until i) {
// 只有前面的数字 nums[j] 比当前数字 nums[i] 小，
// 才能接到 nums[i] 前面，形成递增子序列
if (nums[j] < nums[i]) {
// 如果把 nums[i] 接在 nums[j] 后面，
// 长度就是 dp[j] + 1
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
// 更新全局最长长度
ans = maxOf(ans, dp[i])
}
return ans
}
}
这题最关键的一句话是： dp[i] 表示“以 nums[i] 结尾”的最长递增子序列长度。 不是“前 i 个数字的最长长度”，而是必须以当前这个数字结尾。这点想明白，公式就自然了。
核心思路： 贪心 + 二分查找
假设你有一列数字，你想拼出一个最长的递增序列。你会怎么做？
你会尽量让每个位置的数字尽可能小，这样后面更容易接上更大的数字。
例如 [10,9,2,5,3,7,101,18]： - 看到 10，你先记下“长度为1的递增子序列末尾最小可以是10”。 - 看到 9，它比10小，所以“长度为1的递增子序列末尾最小可以是9”（更新）。 - 看到 2，再次更新为2。 - 看到 5，它比2大，所以你可以得到一个长度为2的递增子序列 [2,5]，记下“长度为2的末尾最小是5”。 - 看到 3，它比5小，但比2大，所以它可以替换掉5，使“长度为2的末尾最小变成3”。 - 看到 7，它比3大，可以扩展成长度为3的子序列 [2,3,7]，记下“长度为3的末尾最小是7”。 - 看到 101，扩展成长度为4，末尾101。 - 看到 18，它比101小但比7大，所以它可以替换101，使“长度为4的末尾最小变成18”。 最终最长长度为4。
O(n log n)
复杂度
- 时间复杂度: O(n^2)，因为每个位置都要看它前面的数字。
- 空间复杂度: O(n)，因为用了一个 dp 数组。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!