图解一道腾讯笔试算法题：「最长上升子序列」

╰半夏微凉° 2023-06-18 14:51 4阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 五分钟学算法

今天分享的题目来源于 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]` 的值就是它们的最大值加 1 。即比当前数要小的那些里头，找最大的，然后加 1 。

于是状态转移方程是：`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` 的那个数，可以使用“二分法”

![format_png 1][] ![format_png 2][] LeetCode 第 300 题：最长上升子序列-2 ![format_png 3][]

*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;
        }
    }

**复杂度分析：**

*  时间复杂度：????(????log????)。
 *  空间复杂度：????(????)。

![音符][format_png 4]

**有热门推荐????**

1.【程序员】[我们就必须承认：这个世界上，有很多问题，就是无解的][Link 1]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了！][Link 2]

![format_png 5][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJkSFhBNHBrVURtVmM5UHp0M0Z5ODRQcVVjdWliTlBsd2g0T1ExT3A3VHFiU1hhMUgwRGtFOWxXajd6ck5zUlZlQWliM0VmcWVLc3BxUS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJkSFhBNHBrVURtVmM5UHp0M0Z5ODR0Z3p2aHNTNDN3elNnVks3ZXI2ZUN1VE1NNEUwekpFUDlQQ0o5ZUNLdTZLSFBMU0k1TTRQN3cvNjQwP3d4X2ZtdD1qcGVn?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJkSFhBNHBrVURtVmM5UHp0M0Z5ODRoeVM2M3hmQ0xyTVRiRGg3Q1JINWs5Q0t5S3F1bWliVXViTEsxY3JjOWliWFRUVG5rV3MyU0FSdy82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L2NaVjJoUnB1QVBpYUpRWFdHeUM5d3JVeklpY2liZ1hheXJnaWJUWWFyVDNBMXl6dHRidGFPMEpsVjIxd01xcm9HWVQzUXRQcTJDN0hNWXN2aWNTQjJwN2RUQmcvNjQwPw?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/100978627
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/100137152
[KMP]: https://blog.csdn.net/kexuanxiu1163/article/details/97071390
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103051357
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVR1U2ljRUtJcWdpYU9FdG9KaWEwTGcxYTJkWkVLcXlwYzlFcDUzVkpsb0Vobzg4VkdYeVpFSHB2d1paVXR6VnR2RTVJRWliQU5kbFdwUVJRLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png