图解一道腾讯笔试算法题：「最长上升子序列」
今天分享的题目来源于 LeetCode 第 300 号问题：最长上升子序列。这道题在 腾讯 笔试中出现过 3 次。
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(nlog n) 吗?
题目解析
首先仔细审题，明确题目中的条件。
1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；
2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列，因为 3 重复了，所以不是“严格上升”的。
一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 ?((2^?)∗?)。
这个问题具有最优子结构，因此可以考虑使用动态规划完成。
方法一：动态规划
定义状态：dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择 以数字 nums[i] 结尾 可以获得的最长上升子序列的长度。注意：以第 i 个数字为结尾，即 要求 nums[i] 必须被选取。反正一个子序列一定会以一个数字结尾，那我就将状态这么定义，这一点是常见的。
状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍，如果当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了，dp[i] 的值就是它们的最大值加 11。即比当前数要小的那些里头，找最大的，然后加 11 。
于是状态转移方程是：dp(i) = max{1 + dp(j) if j < i and dp[i] > dp[j]}。
最后不要忘了，扫描一遍这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。
Python 代码：
class Solution:
# 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
# 那么题目要求的，就是这个 dp 数组中的最大者
# 以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例
# dp 的值：1 1 1 2 2 3 4 4
def lengthOfLIS(self, nums):
size = len(nums)
# 特判
if size <= 1:
return size
dp = [1] * size
for i in range(1, size):
for j in range(i):
if nums[i] > nums[j]:
# + 1 的位置不要加错了
dp[i] = max(dp[i], dp[j] + 1)
# 最后要全部一看遍，取最大值
return max(dp)Java 代码：
import java.util.Arrays;
public class Solution {
//【关键】将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
// 那么题目要求的，就是这个 dp 数组中的最大者
// 以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例：
// dp 的值：1 1 1 2 2 3 4 4
// 注意实现细节。
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
// 状态的定义是：以 i 结尾的最长上升子序列的长度
// 状态转移方程：之前比最后那个数字小的最长上升子序列的长度 + 1
int[] dp = new int[len];
// 如果只有 1 个元素，那么这个元素自己就构成了最长上升子序列，所以设置为 1 是合理的
Arrays.fill(dp, 1);
// 从第 2 个元素开始，逐个写出 dp 数组的元素的值
for (int i = 1; i < len; i++) {
int curVal = nums[i];
// 找出比当前元素小的哪些元素的最小值
for (int j = 0; j < i; j++) {
if (curVal > nums[j]) {
dp[i] = Integer.max(dp[j] + 1, dp[i]);
}
}
}
// 最后要全部走一遍，看最大值
int res = dp[0];
for (int i = 0; i < len; i++) {
res = Integer.max(res, dp[i]);
}
return res;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
Solution solution = new Solution();
int lengthOfLIS = solution.lengthOfLIS(nums);
System.out.println(lengthOfLIS);
}
}复杂度分析：
- 时间复杂度：?(?2)。
- 空间复杂度：?(?)。
这道题还有一个时间复杂度为 ?(?log?)的解法，如下。
方法二：贪心算法（二分法）
思路：每一次来一个新的数 num，在 tail 数组（tail 数组的定义在下面的示意图中有）中找大于等于 num 的那个数，试图让它变小，以致于新来的数有更多的可能性接在它后面，成为一个更长的“上升子序列”，这是“贪心算法”的思想。
在 tail 数组中找大于等于 num 的那个数，可以使用“二分法”
LeetCode 第 300 题：最长上升子序列-2
Python 代码：
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return size
tail = []
for num in nums:
# 找到大于等于 num 的第 1 个数
l = 0
r = len(tail)
while l < r:
mid = l + (r - l) // 2
if tail[mid] < num:
l = mid + 1
else:
r = mid
if l == len(tail):
tail.append(num)
else:
tail[l] = num
return len(tail)Java 代码：
public class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
// 这个数组实际上的长度，就是最后所求
int[] tail = new int[len];
int end = 0;
tail[0] = nums[0];
for (int i = 1; i < len; i++) {
if (nums[i] > tail[end]) {
end++;
tail[end] = nums[i];
} else {
// 使用二分搜索法来做这件事情
// 数组长度不变，一定会更新一次
// 特殊例子：1 2 3 4 5 7 7 7 7 7 7 7 （只是举个例子，这道题不会出现这种情况），来了一个 6
// 我要将从左到右边数第 1 个大于 6 的数字更新为 6
int left = 0;
int right = end;
int target = nums[i];
while (left < right) {
int mid = left + (right - left) / 2;
if (tail[mid] < target) {
// 只要比目标值要小，我们要找的位置就至少是当前位置 + 1
left = mid + 1;
} else {
assert tail[mid] >= target;
// 大于目标值，我们不能盲目向前走，因为向前走很可能，值会变得比目标值小
right = mid;
}
}
tail[right] = target;
}
}
return end + 1;
}
}