【C/C++】300. 最长递增子序列（经典题目）

我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第1篇文章，点击查看活动详情

---

题目链接：300. 最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

提示:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

示例 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

整理题意

题目给定一个整数数组 nums，找到 nums 中 最长严格递增子序列 的长度。

子序列不要求连续，子数组才要求连续。

进阶要求时间复杂度为：O(nlog⁡n)O(n \log n)O(nlogn)。

解题思路分析

动态规划

令 dp[i] 表示为以数字 nums[i] 结尾（包括 nums[i]）的最长上升子序列的长度。那么我们从头到尾遍历数组，对应 nums[i] 来说，我们仅需遍历 [0, i)（左闭右开区间）中所有整数，选取小于 nums[i] 的整数来跟新 dp[i] 的长度即可，遍历过程中维护 dp[i] 的最大值即可。

贪心+二分

贪心思维： 我们要使上升子序列尽可能的长，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。所以 定义数组 dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。

贪心的关键在于： 定义数组 dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值 ，即在数组 [1,2,3,4,5,6] 中长度为 3 的上升子序列可以为 [1,2,3] 也可以为 [2,3,4] 等等但是dp[3]=3，即子序列末尾元素最小为 3。

这是因为在上述数组中长度为 3 的上升子序列为 [1,2,3] 的利用价值大于其他长度为 3 的上升子序列，也就是 给后面留更多的空间。

具体实现

动态规划

1. 令 dp[i] 表示为以数字 nums[i] 结尾（包括 nums[i]）的最长上升子序列的长度；
2. 第一层循环从左到右遍历数组中的整数，对于每个整数寻找以其结尾的最长上升子序列的长度；
3. 第二层循环遍历 [0, i)（左闭右开区间）中所有整数，如果 nums[j] < nums[i] 那么我们就跟新 dp[i] = max(dp[i], dp[j] + 1)；
4. 遍历的过程中用 ans 记录 dp[i] 的最大值，最后返回 ans 即可。

贪心+二分

1. 定义数组 dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值;
2. 遍历数组 nums[i]，对于每个 nums[i] 来说，如果 nums[i] 大于 dp 数组最后一个数，那么直接让 nums[i] 接在 dp 数组后面即可，保证 dp 数组为单调递增数组。
3. 如果 nums[i] 小于 dp 数组最后一个数，那么就在 dp 数组中二分查找第一个大于等于 nums[i] 的整数位置，nums[i] 代替其的位置。（因为 dp 数组为单调递增数组，所以可以使用二分查找，又因为 nums[i] 大于 dp 数组最后一个数，所以一定能在 dp 数组中找到第一个大于等于 nums[i] 的整数位置。）

代替其位置就是为了给后面更多的空间，可以形象的比喻为：一个新员工和一个老员工价值相当，老员工就可以走了，因为新员工被榨取的剩余空间更多。

1. 最后 dp 数组的长度即为 nums 中 最长严格递增子序列 的长度。

复杂度分析

• 时间复杂度：
  • 动态规划的时间复杂度为 O(n2)O(n^2)O(n2)，其中 nnn 为数组 nums 的长度。动态规划的状态数为 nnn，计算状态 dp[i] 时，需要 O(n)O(n)O(n) 的时间遍历 dp 数组 [0, i - 1] 的所有状态，所以总时间复杂度为 O(n2)O(n^2)O(n2)。
  • 贪心+二分的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。数组 nums 的长度为 nnn，我们依次用数组中的元素去更新 dp 数组，而更新 dp 数组时需要进行 O(log⁡n)O(\log n)O(logn) 的二分搜索，所以总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。
• 空间复杂度：两种方法都需要 O(n)O(n)O(n) 的空间复杂度，需要额外使用长度为 nnn 的 dp 数组。

代码实现

动态规划

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int dp[n], ans = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

贪心+二分

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ans; ans.clear();
        for(int &num : nums){
            if(ans.size() == 0 || ans.back() < num){
                ans.emplace_back(num);
            }
            else{
                int pos = lower_bound(ans.begin(), ans.end(), num) - ans.begin();
                ans[pos] = num;
            }
        }
        return ans.size();
    }
};

总结

• 该题是较为经典的寻找 最长递增子序列 的题目，是作为很多题目衍生的母题，也就是在此题基础上进行进一步扩展的。
• 动态规划的思想较为容易理解，但在代码实现上时间复杂度较差；而对于 贪心+二分搜索 的方法需要掌握，因为其在同样空间复杂度的情况下时间复杂度上是更优的，在对于其他衍生题目来说也是更有优势的。
• 测试结果：

通过对比两种方法的测试结果，可以看出 贪心+二分 的时间复杂度明显优于动态规划的方法。

结束语

聪明的人很多，靠谱的人却难得。一个靠谱的人，一定是负责任、有担当的人，也是坚守底线、有原则的人。许下承诺就尽力去实现，答应的事情绝不含糊，愿我们都能成为靠谱的人。新的一天，加油！