跳转至

300 最长递增子序列

动态规划

思路:

  • 题目求最长递增子序列,假设我们已经找了k个元素形成了子序列a,我们发现,如果想要继续增加新元素,需要关注子序列a最后一个元素nums[i],比较nums[j]与nums[i]的关系(j > i)。这一步骤本质上关注的是子序列的末尾元素,对于子序列其他元素不关心。因此我们围绕末尾元素建模。
  • 我们将dp[i]设置为第i个元素结尾的最长递增子序列长度,确认dp[i]含义后很容易得到递推公式
  • 递推公式:

    遍历nums[i]之前的元素nums[j],比较两者关系,如果nums[i] > nums[j],dp[i] = dp[j] + 1

    // 伪代码
    if(nums[i] > nums[j]) {
      dp[i] = max(dp[j] + 1),j从0遍历到i - 1
    }
    res = max(dp[i]),i从0遍历到i - 1
    
  • 遍历顺序:从左到右或从右到左都可以,只需要将索引[0, i - 1]的元素遍历一遍,默认从左到右
  • 初始化:每个元素结尾的最长递增子序列长度至少为1,即该元素本身,所以\(dp[i] = 1, i \in [0, n - 1]\)
  • 结果:取\(res = max(dp[i]), i \in [0, n - 1]\)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // dp[i]表示以nums[i]结尾的最长严格递增子序列的长度
        // 默认为1,仅包含nums[i]
        vector<int> dp(n, 1);
        // 取dp[i]最大值为结果
        int res = 1;
        for(int i = 0; i < n; i++){
            // 遍历j从0到i - 1
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

时间复杂度:\(O(n^2 )\),其中 n 为数组 nums 的长度。动态规划的状态数为 n,计算状态 dp[i] 时,需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态,所以总时间复杂度为 \(O(n^2)\)。

空间复杂度:\(O(n)\),需要额外使用长度为 n 的 dp 数组

贪心 + 二分查找

这个优化方法很容易想到,我们想要得到尽可能长的递增序列,就需要选择和当前末尾元素nums[i]尽可能大小相近的元素,从而减小序列上升速度

选择和当前末尾元素nums[i]尽可能大小相近的元素

  • 这就是贪心的思路,我们寻找比nums[i]大的元素集合,再从中找到最小的元素即可

d[i] 表示长度为i的递增序列末尾元素的最小值

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        vector<int> d(n + 1, 0);
        int len = 1;
        d[len] = nums[0];
        for(int i = 1; i < n; i++){
            if(nums[i] > d[len]){
                d[++len] = nums[i];
            }
            else{
                // 通过二分查找 找到第一个大于等于nums[i]的元素
                // 注意这里是二分查找的区间为[d.begin() + 1, d.begin() + len + 1]
                auto it = lower_bound(d.begin() + 1, d.begin() + len + 1, nums[i]);
                // pos为第一个大于等于nums[i]的元素的索引
                int pos = distance(d.begin(),it);
                // 更新d[pos]为nums[i]
                d[pos] = nums[i];
            }
        }
        return len;
    }
};