leetcode刷题笔记-674.最长连续递增序列。

题目

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

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

1
2
3
4
5
6
7
8
9
10
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示

1
2
1 <= nums.length <= 104
-109 <= nums[i] <= 109

思路和代码

这道题相比300.最长递增子序列多了一个连续的要求，这样一来思路其实就简单多了。

定义dp数组含义为i和i之前的最长递增子序列的长度（准确来说是以i为结尾的最长递增子序列的长度，子序列开始的下标不确定）

我们只需要判断当前位是不是比前一位大，如果比前一位大，那么就可以沿用之前的结果

1
2
3
if(nums[i] > nums[i-1]){
	dp[i] = dp[i-1]+1;
}

这样就能很容易的写出代码来，时间和空间复杂度都是O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ret = 1; // 结果长度
        // 最开始的时候，每一位的最长子序列认为是它自己
        vector<int> dp(nums.size(), 1);
        // 从1开始遍历，因为0只有一个元素，没有意义
        for (int i = 1; i < nums.size(); i++) {
            // 因为要求连续，所以只需要判断前一位就够了。
            if(nums[i] > nums[i-1]){
                dp[i] = dp[i-1]+1; 
            }
            // 更新结果最大值
            if (dp[i] > ret) {
                ret = dp[i];
            }
        }
        return ret;
    }
};

image.png

优化

这个代码可以进行优化，因为每一次的递推只和前一个数字有关系，我们直接用一个变量来记录就够了，空间复杂度降低为O(1)。

这样做就有点类似贪心的思路，我们认为当前位大于前一位就是一个上升子序列的局部最优，最终的全局最优就是找到一个最长的连续上升子序列。官方的贪心题解本质上和下面的写法是一样的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ret = 1; // 结果长度
        int cur = 1; // 当前的长度
        // 从1开始遍历，因为0只有一个元素，没有意义
        for (int i = 1; i < nums.size(); i++) {
            // 因为要求连续，所以只需要判断前一位就够了。
            if (nums[i] > nums[i - 1]) {
                cur = cur + 1;
            } else {
                cur = 1; // 其他情况，重置为1，重新开始计算
            }
            // 更新结果最大值
            if (cur > ret) {
                ret = cur;
            }
        }
        return ret;
    }
};

image.png

顺带贴一下官方题解的贪心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = max(ans, i - start + 1);
        }
        return ans;
    }
};

// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/solutions/573383/zui-chang-lian-xu-di-zeng-xu-lie-by-leet-dmb8/