674. 最长连续递增序列

题目描述

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

连续递增的子序列 可以由两个下标 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⁴
-10⁹ <= nums[i] <= 10⁹

解法

方法一：一次遍历

思考

连续递增子数组必须相邻，不必做一般 LIS。一次扫描即可。

用 \(cnt\) 记当前段长度，相邻递增则加一并更新答案，否则重置为 \(1\)。

我们可以遍历数组 \(nums\)，用变量 \(cnt\) 记录当前连续递增序列的长度。初始时 \(cnt = 1\)。

然后，我们从下标 \(i = 1\) 开始，向右遍历数组 \(nums\)。每次遍历时，如果 \(nums[i - 1] < nums[i]\)，则说明当前元素可以加入到连续递增序列中，因此令 \(cnt = cnt + 1\)，然后更新答案为 \(ans = \max(ans, cnt)\)。否则，说明当前元素无法加入到连续递增序列中，因此令 \(cnt = 1\)。

遍历结束后，返回答案 \(ans\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(nums\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRustPHP

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = cnt = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 1
        return ans

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 1;
        for (int i = 1, cnt = 1; i < nums.length; ++i) {
            if (nums[i - 1] < nums[i]) {
                ans = Math.max(ans, ++cnt);
            } else {
                cnt = 1;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 1;
        for (int i = 1, cnt = 1; i < nums.size(); ++i) {
            if (nums[i - 1] < nums[i]) {
                ans = max(ans, ++cnt);
            } else {
                cnt = 1;
            }
        }
        return ans;
    }
};

func findLengthOfLCIS(nums []int) int {
    ans, cnt := 1, 1
    for i, x := range nums[1:] {
        if nums[i] < x {
            cnt++
            ans = max(ans, cnt)
        } else {
            cnt = 1
        }
    }
    return ans
}

function findLengthOfLCIS(nums: number[]): number {
    let [ans, cnt] = [1, 1];
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i - 1] < nums[i]) {
            ans = Math.max(ans, ++cnt);
        } else {
            cnt = 1;
        }
    }
    return ans;
}

impl Solution {
    pub fn find_length_of_lcis(nums: Vec<i32>) -> i32 {
        let mut ans = 1;
        let mut cnt = 1;
        for i in 1..nums.len() {
            if nums[i - 1] < nums[i] {
                ans = ans.max(cnt + 1);
                cnt += 1;
            } else {
                cnt = 1;
            }
        }
        ans
    }
}

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findLengthOfLCIS($nums) {
        $ans = 1;
        $cnt = 1;
        for ($i = 1; $i < count($nums); ++$i) {
            if ($nums[$i - 1] < $nums[$i]) {
                $ans = max($ans, ++$cnt);
            } else {
                $cnt = 1;
            }
        }
        return $ans;
    }
}

方法二：双指针

思考

计数扫描与双指针等价：外指针停在段首，内指针滑到段尾，长度 \(j-i\)，再把外指针跳到 \(j\)。

我们也可以用双指针 \(i\) 和 \(j\) 找到每一段连续递增序列，找出最长的连续递增序列的长度作为答案。