0674. 最长连续递增序列 #

标签：数组
难度：简单

题目大意 #

描述：给定一个未经排序的数组 nums。

要求：找到最长且连续递增的子序列，并返回该序列的长度。

说明：

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

示例：

1
2
3


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

解题思路 #

思路 1：动态规划 #

1. 定义状态 #

定义状态 dp[i] 表示为：以 nums[i] 结尾的最长且连续递增的子序列长度。

2. 状态转移方程 #

因为求解的是连续子序列，所以只需要考察相邻元素的状态转移方程。

如果一个较小的数右侧相邻元素为一个较大的数，则会形成一个更长的递增子序列。

对于相邻的数组元素 nums[i - 1] 和 nums[i] 来说：

如果 nums[i - 1] < nums[i]，则 nums[i] 可以接在 nums[i - 1] 后面，此时以 nums[i] 结尾的最长递增子序列长度会在「以 nums[i - 1] 结尾的最长递增子序列长度」的基础上加 1，即 dp[i] = dp[i - 1] + 1。
如果 nums[i - 1] >= nums[i]，则 nums[i] 不可以接在 nums[i - 1] 后面，可以直接跳过。

综上，我们的状态转移方程为：dp[i] = dp[i - 1] + 1，nums[i - 1] < nums[i]。

3. 初始条件 #

默认状态下，把数组中的每个元素都作为长度为 1 的最长且连续递增的子序列长度。即 dp[i] = 1。

4. 最终结果 #

根据我们之前定义的状态，dp[i] 表示为：以 nums[i] 结尾的最长且连续递增的子序列长度。则为了计算出最大值，则需要再遍历一遍 dp 数组，求出最大值即为最终结果。

思路 1：动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [1 for _ in range(size)]

        for i in range(1, size):
            if nums[i - 1] < nums[i]:
                dp[i] = dp[i - 1] + 1
        
        return max(dp)

思路 1：复杂度分析 #

时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$，最后求最大值的时间复杂度是 $O(n)$，所以总体时间复杂度为 $O(n)$。
空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。

思路 2：滑动窗口（不定长度） #

设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口内为连续递增序列。使用 window_len 存储当前窗口大小，使用 max_len 维护最大窗口长度。
一开始，left、right 都指向 0。
将最右侧元素 nums[right] 加入当前连续递增序列中，即当前窗口长度加 1（window_len += 1）。
判断当前元素 nums[right] 是否满足连续递增序列。
如果 right > 0 并且 nums[right - 1] >= nums[right] ，说明不满足连续递增序列，则将 left 移动到窗口最右侧，重置当前窗口长度为 1（window_len = 1）。
记录当前连续递增序列的长度，并更新最长连续递增序列的长度。
继续右移 right，直到 right >= len(nums) 结束。
输出最长连续递增序列的长度 max_len。

思路 2：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        size = len(nums)
        left, right = 0, 0
        window_len = 0
        max_len = 0
        
        while right < size:
            window_len += 1
            
            if right > 0 and nums[right - 1] >= nums[right]:
                left = right
                window_len = 1

            max_len = max(max_len, window_len)
            right += 1
            
        return max_len

思路 2：复杂度分析 #

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。