有关递增子序列的几个问题

昨天在Leetcode上刷了几道关于递增子序列的题,在discussion里看到一些非常简洁高效的代码,故学习记录于此。

递增三元子序列

给定一个存放整数的vector,求其是否存在长度为3的递增三元子序列,时间复杂度的要求是$O(n)$,空间复杂度的要求是$O(1)$。
既然时间复杂度是$O(n)$,就要求一遍遍历要得到答案,一种可行解的方式就是,使用两个变量存储三元递增子序列的前两个。设两变量分别为c1、c2,初值设为INT_MAX,设每一次循环取的数是x,若x比c1小,则将c1更新为x,否则判断x是否比c2小,是则更新c2,否则递增三元子序列找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool increasingTriplet(vector<int> &nums) {
int c1 = INT_MAX, c2 = INT_MAX;
for (int num : nums) {
if (num <= c1) {
c1 = num;
} else if (num <= c2) {
c2 = num;
} else {
return true;
}
}
return false;
}

算法很巧妙,巧在以下几点:

  • 维护两个变量,保存递增三元子序列的前两个,根据第三个元素来判断,因此只需遍历一遍
  • 当第三个元素的值都比前两个大时,就找到了满足的解
  • 当第三个元素的值比第一个值小,为什么要直接替换第一个元素的值?因为若后面还存在比第一个元素小的两个值,那么当前第三个元素也肯定比那两个值小,也可以构成解
  • 当第三个元素的值介于前两者之间,则更新第二个元素的值,原理同上

最长递增子序列的两种解法

给定一个存放整数的vector,确定其最长递增子序列的长度。常有$O(n^2)$和$O(nlogn)$两种解法。

时间复杂度$O(n^2)$

使用dp[n]来记录以nums[n]结尾的最长递增子序列的长度。代码分为两层循环,外层循环i从1到n-1,更新dp[i]的值;内层循环j从0到i-1,找到最大的dp[j],用其更新dp[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLIS(vector<int> &nums) {
int n = nums.size(), ans = 0;
if (n == 1) return 1;
vector<int> dp(n, 0);
for (int i = 1; i < n; i++) {
int k = 0;
for (int j = 0; j < i; j++)
if (nums[j] < nums[i] && k < dp[j])
k = dp[j];
dp[i] = ++k;
ans = max(ans, dp[i]);
}
return ans;
}

时间复杂度$O(nlogn)$

这里用到了std::lower_bound函数,此函数返回一个迭代器,指向参数值应该插入的位置。维护一个集合res,遍历一遍vector,每次获得将元素插入改集合的迭代器,若迭代器指向res集合尾部,则将该元素加入res集合,否则直接更新res集合中对应位置的值。
为什么这样可行?其实本质还是让比较小的元素在res集合中,以{10,9,2,5,3,7,101,18}为例,res集合中一开始是{10},然后是{9},然后是{2},然后是{2,5},然后是{2,3},然后是{2,3,7},然后是{2,3,7,101},最后是{2,3,7,18}。
值得注意的是,这样到最后res集合中并不一定是最长递增子序列的值,但是长度是一样的。

1
2
3
4
5
6
7
8
9
int lengthOfLIS_ex(vector<int> &nums) {
vector<int> res;
for (unsigned int i = 0; i < nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if (it == res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}

文章目录
  1. 1. 递增三元子序列
  2. 2. 最长递增子序列的两种解法
    1. 2.1. 时间复杂度$O(n^2)$
    2. 2.2. 时间复杂度$O(nlogn)$
|