674 最长连续递增序列（双指针）

我会带着你远行 2022-09-02 12:55 143阅读 0赞

**1. 问题描述：**

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums\[i\] < nums\[i + 1\] ，那么子序列 \[nums\[l\], nums\[l + 1\], ..., nums\[r - 1\], nums\[r\]\] 就是连续递增子序列。

**示例 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 <= nums.length <= 10 ^ 4  
\-10 ^ 9 <= nums\[i\] <= 10 ^ 9  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence

**2. 思路分析：**

分析题目可以知道我们需要找到所有连续递增的序列，在所有连续递增的序列中找到最长的那个序列即可。这里我们可以使用**双指针**来找连续一段递增的数字，声明两个指针i，j，指针i指向当前的数字nums\[i\]，指针j指向i的下一个位置的数字，只要当前数字大于前一个数字那么指针j就往后走，最终j - i就是以当前数字nums\[i\]开始连续递增的序列长度，在求解的过程中维护当前连续递增序列长度的最大值即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findLengthOfLCIS(self, nums: List[int]) -> int:
            res = 1
            i, n = 0, len(nums)
            while i < n - 1:
                # 主要当前的数字大于前一个数字那么就找到以当前数字开始最长连续递增的一段
                if nums[i] < nums[i + 1]:
                    j = i + 1
                    while j < n and nums[j] > nums[j - 1]: j += 1
                    # 维护最大值
                    res = max(res, j - i)
                    i = j
                else:
                    i += 1
            return res