leetcode刷题笔记-300.最长递增子序列。

题目

https://leetcode.cn/problems/longest-increasing-subsequence/description/

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

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

1
2
3
4
5
6
7
8
9
10
11
12
示例 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
2
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

思路一：动态规划

思路说明

先理解题目说的两个概念

  1. 严格递增：[1,2,3,4]是严格递增，[1,2,2,3]不是严格递增；
  2. 子序列：数组中的一部分，删除某些元素后得到的序列，比如[1,2,3]数组，删除2后可以得到子序列1,3，也可以不删除元素1,2,3也是它的子序列。但是3,1或者2,1都不是这个数组的子序列，因为元素的顺序和源数组中元素的顺序不一致；

了解定义了，就可以上动态规划的思路了。

我们定义dp数组的含义为源数组中下标i和i之前的最长递增子序列的长度（这一点和第五题最长回文子串的思路类似）。易得dp数组应该全部初始化为1，即认为最开始的时候，每一位之前的最长递增子序列是他自己。

那么递推方程应该是咋样的呢？分为两种情况

  • 当前位元素大于前一位，那么当前的最长子序列长度应该是前一位的最长子序列长度+1；
  • 当前位元素小于前一位，说明不能沿用之前的结果，当前的最长子序列长度得保持不变；

可得递推公式dp[i] = max(dp[i], dp[j] + 1)，判断逻辑如下

1
2
3
4
5
6
if(nums[i] > nums[i-1]){
	// 大于，沿用之前的结果
	dp[i] = max(dp[i],dp[i-1]+1);
}else{
	// 小于或者等于，不对dp[i]操作
}

但是这样判断还不够，因为子序列是允许删除某些元素的，对于遍历一个数组而言，它就是允许遍历不连续，所以我们需要用两层循环来处理，外层循环i从1开始遍历nums数组（从0开始没有意义），内层循环j从0开始遍历到i-1。

1
2
3
4
5
6
7
8
9
10
for(int i = 1;i<nums.size();i++){
	for(int j = 0;j<i;j++){
		if(nums[i] > nums[j]){
			// 大于，沿用之前的结果
			dp[i] = max(dp[i],dp[j]+1);
		}else{
			// 小于或者等于，不对dp[i]操作
		}
	}
}

为什么我们需要用max来计算呢？因为每一次对i的递推都需要遍历i之前的所有元素才能递推出来，可能会出现前面某一位的最长递增子序列结果更大的情况，我们必须要保证得到的是最长的那一个子序列值。

同时，我们的遍历是从左往右的，当遍历到i的时候，i之前的那些元素在dp里面已经被正常计算出来最长的子序列长度了，所以我们只需要判断一次nums[i] > nums[j]，就可以沿用之前的结果了。

完整代码

现在就可以写最终的代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int ret = 1;// 结果长度
        // 最开始的时候，每一位的最长子序列认为是它自己
        vector<int> dp(nums.size(),1);
        // 从1开始遍历，因为0只有一个元素，没有意义
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    // 大于，沿用之前的结果
                    dp[i] = max(dp[i], dp[j] + 1);
                } 
            }
            // 更新结果最大值
            if(dp[i] > ret){
                ret = dp[i];
            }
        }
        return ret;
    }
};

时间复杂度是O(n^2)，空间复杂度是O(n)。

image.png

和这道题类似的是 674. 最长连续递增序列，其中要求子序列必须是连续的，中间不能中断。我会在另外一篇博客中写674的题解。

思路二：二分法+结果集数组

思路说明

首先我们维护一个结果集的数组，将原数组的第一个元素入结果集数组，然后从下标1开始遍历原数组nums，使用二分法来进行当前元素的目标位置的查询：

  • 如果当前元素比结果集数组末位还大，则直接尾插；
  • 在结果集中找到比当前元素大的第一个元素（比当前元素大的最靠前的元素），将当前元素替换进去；

这样遍历完毕之后，我们得到的结果集数组可能不是最终的最长递增子序列，但是它的长度是对的。本题也只需要你返回长度。

完整代码

完整代码如下，使用循环加二分法的时间复杂度是O(N*Log(N))；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 结果集
        vector<int> retV;
        retV.emplace_back(nums[0]);
        // 从1开始遍历，因为0只有一个元素，没有意义
        for (int i = 1; i < nums.size(); i++) {
            // 如果nums[i]比末尾还大直接插入
            if (retV.back() < nums[i]) {
                retV.emplace_back(nums[i]);
                continue;
            }
            // 二分法找到结果集中比当前元素大的第一个元素
            int left = 0, right = retV.size() - 1;
            while (left < right) {
                int mid = (right + left) / 2;
                if (retV[mid] < nums[i]) {
                    left = mid + 1; // 这里需要加一，走到下一位
                } else {
                    right = mid;
                }
            }
            // 循环结束之后，left是第一个比nums[i]大的数
            retV[left] = nums[i];
        }
        return retV.size();
    }
};

image.png

上述代码可以简写成下面这样，思路是一样的。利用了cpp的内置函数lower_bound，该函数的作用和我们上面写的二分法一致，用于找数组中第一个比n大的数字。同时还有一个upper_bound，用于找数组中第一个比n小的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 结果集
        vector<int> retV;
        for (auto& n : nums) {
            auto it = lower_bound(retV.begin(), retV.end(), n);
            if (it != retV.end()) {
                *it = n;
            } else {
                retV.emplace_back(n);
            }
        }
        return retV.size();
    }
};

不过这是我第一次见到lower_bound/upper_bound这两个函数，感觉平时用的很少捏。

思路三：回溯

思路说明

回溯方法就比较直接了，我们使用回溯获取数组子序列的基本模板，然后在单层循环中加上对数字大小的判断即可。如果当前选用的数字比结果集数组中末尾还小，则不插入，否则插入其中。这样能保证单调递增的特性。

使用这种方式，其实可以把数组中所有递增的子序列筛选出来。详见我的回溯博客中的leetcode491题目。

在面试的时候我就被考到了最长递增子序列的题目，题目要求返回最长递增子序列，如果有多个相同长度的最长递增子序列，则还需要返回字典序最小的那个。

完整代码

这里直接贴出回溯的代码，不做思路说明了。第一个参数是源数组，第二个参数是结果集，第三个参数是每层回溯开始的下标。

回溯的终止条件是startIndex越界，此时将结果集和预置的最长递增子序列结果maxV进行对比，如果长度更长直接赋值给maxV，如果长度相同，则还需要遍历判断字典序，选出字典序最小的返回。

因为leetcode300题目只需要让我们返回子序列的长度，所以不需要这么麻烦。我这里的处理给面试的时候那道需要返回子序列的题目做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
vector<long long> maxV;
void travel(const vector<long long> &v, vector<long long> &retV, size_t startIndex)
{
    if (startIndex >= v.size())
    {
        if (retV.size() > maxV.size())
        {
            maxV = retV;
        }
        if (retV.size() == maxV.size())
        {
            // 相同长度需要取字典序最小的
            for (size_t j = 0; j < maxV.size(); j++)
            {
                if (maxV[j] > retV[j])
                {
                    maxV = retV;
                    break;
                }
            }
        }
        return;
    }
    for (size_t i = startIndex; i < v.size(); i++)
    {
        if (!retV.empty() && v[i] <= retV.back())
        {
            continue;
        }
        retV.push_back(v[i]);
        travel(v, retV, i + 1);
        retV.pop_back();
    }
    // 这里也需要判断，可能出现后续元素都比retV.back()小导致循环结束的情况
	if (retV.size() > maxV.size())
	{
		maxV = retV;
	}
	if (retV.size() == maxV.size())
	{
		// 相同长度需要取字典序最小的
		for (size_t j = 0; j < maxV.size(); j++)
		{
			if (maxV[j] > retV[j])
			{
				maxV = retV;
				break;
			}
		}
	}
}

回溯思路的时间复杂度是O(N^2)，在leetcode上会超时。面试的题目要求返回完整的子序列，个人还没想到能使用回溯以外的方式。一般情况下面试也不会给出这么长的测试用例，所以应该是出现不了超时的情况的。

注意，上文的第二种思路返回的子序列数组不一定是正确的！它只能保证长度正确！

image.png