HHot 100C++ 图解

300. 最长递增子序列

中等 动态规划(一维) 4 帧动画 在力扣上做

一句话套路tails[k]=长度 k 的最小结尾 + lower_bound

题目描述

给你一个整数数组 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

 

提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

 

进阶:

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

思路

时间O(n^2)
空间O(n)

解法 A(O(n^2))

dp[i] = 以 nums[i] 结尾的 LIS 长度,dp[i]=max(dp[j]+1) for j<i 且nums[j]<nums[i]。注意答案是 max(dp[i]),不是 dp[n-1]。

解法 B(O(n log n))

tails[k] = 长度为 k+1 的递增子序列的「最小结尾」。

它本身不是 LIS,但长度就是 LIS 长度。用 lower_bound 找替换位置:能替换说明存在同样长度但结尾更小的子序列 —— 结尾越小越有潜力延长。

严格递增用 lower_bound;若求「非降」子序列改用 upper_bound。

变体

Q673 最长递增子序列的个数;Q354 俄罗斯套娃(排序后转 LIS)。

图解

10 0 9 1 2 2 5 3 3 4 7 5 101 6 18 7
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp28 行
namespace lc0300 {
class Solution {
 public:
  static int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;  // tails[k]:长度 k+1 的递增子序列的最小末尾
    for (int x : nums) {
      auto it = lower_bound(tails.begin(), tails.end(), x);  // 第一个 >= x
      if (it == tails.end())
        tails.push_back(x);  // 能延长
      else
        *it = x;  // 替换成更小的结尾
    }
    return (int)tails.size();
  }

  static int lengthOfLISDP(vector<int>& nums) {
    const int n = (int)nums.size();
    vector<int> dp(n, 1);
    int best = n ? 1 : 0;
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
      best = max(best, dp[i]);
    }
    return best;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q300_longest_increasing_subsequence15 行
lc0300::Solution s;
vector<int> a{10, 9, 2, 5, 3, 7, 101, 18};
CHECK_EQ(s.lengthOfLIS(a), 4);
CHECK_EQ(s.lengthOfLISDP(a), 4);  // 两种解法必须一致
vector<int> b{0, 1, 0, 3, 2, 3};
CHECK_EQ(s.lengthOfLIS(b), 4);
CHECK_EQ(s.lengthOfLISDP(b), 4);
vector<int> c{7, 7, 7, 7, 7};  // 严格递增 -> 长度 1
CHECK_EQ(s.lengthOfLIS(c), 1);
CHECK_EQ(s.lengthOfLISDP(c), 1);
vector<int> d{4, 10, 4, 3, 8, 9};
CHECK_EQ(s.lengthOfLIS(d), 3);
CHECK_EQ(s.lengthOfLISDP(d), 3);
vector<int> e{1};
CHECK_EQ(s.lengthOfLIS(e), 1);

↑↓ 选择↵ 打开/ 随时唤起