[LeetCode]Ar674. 最长连续递增序列

🚩传送门：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

题目

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

连续递增的子序列 ：如果对于每个 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. 如果下标 且 ，则说明当前元素不大于上一个元素，因此无法继续构成连续递增序列
2. 此时下标范围 的连续子序列是递增序列，其长度为 ，经比较后更新答案
3. 下标 处此时成为另一个新的连续递增序列的开始，因此令 。

复杂度分析

时间复杂度：，其中 是 的长度。需要遍历数组一次。

空间复杂度： ，额外使用的空间为常数。

👀我的代码

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int start = 0;
        //1.依次遍历数组
        for (int i = 1; i < n; i++) {
            //2.如果不构成连续增长序列
            if (nums[i] <= nums[i - 1]) {
                //3.刷新答案
                ans = Math.max(ans, i - start);
                //4.当前下标被更新下一个序列的起点
                start = i;
            }
        }
        //5.防止最后一段构成增长序列,未触发刷新
        return Math.max(ans, n - start);
    }
}

官方代码

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        //0.起始元素必然自己构成1个序列
        int ans = 1;
        int n = nums.length;
        int start = 0;
        //1.依次遍历数组
        for (int i = 1; i < n; i++) {
            //2.当前元素和前面不构成连续增长序列
            if (nums[i] <= nums[i - 1]) {
                //3.当前位置标记起点
                start = i;
            }
            //4.每次 i 的移动都会更新 ans
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}