674. 最长连续递增序列#

题目描述#

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

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

示例 1：

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

示例 2：

1
输入：nums = [2,2,2,2,2]
2
输出：1

提示：

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

解题思路#

核心思想#

用分组循环把数组按「严格递增」分段：段内满足 nums[j+1] > nums[j]。找到递增段起点 i，内层 j 向后扩展直到递增中断，段长度更新答案，i = j + 1。

分组示意（nums = [1,3,5,4,7]）：

1
[1,3,5] | [4,7]
2
   3         2   → 最大 3

算法步骤#

初始化 ans = 0，i = 0。
当 i < n 时：
- j = i，内层 while j+1 < n and nums[j+1] > nums[j] 时 j++；
- ans = max(ans, j - i + 1)，i = j + 1。
返回 ans。

逐步举例#

以 nums = [1,3,5,4,7] 为例：

段	区间	长度
1,3,5	[0,2]	3
4,7	[3,4]	2

最大为 3。注意 3→5 递增、5→4 中断，故两段分开。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def findLengthOfLCIS(self, nums: List[int]) -> int:
6
        n = len(nums)
7
        ans = 0
8
        i = 0
9
        while i < n:
10
            j = i
11
            while j + 1 < n and nums[j + 1] > nums[j]:
12
                j += 1
13
            ans = max(ans, j - i + 1)
14
            i = j + 1
15
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().findLengthOfLCIS([1, 3, 5, 4, 7]), 3)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().findLengthOfLCIS([2, 2, 2, 2, 2]), 1)
16

17

18
if __name__ == '__main__':
19
    unittest.main()