300. 最长递增子序列
一句话套路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)。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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);