题目描述

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

连续递增的子序列 可以由两个下标 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。

作者：力扣 (LeetCode)

链接：https://leetcode.cn/leetbook/read/sliding-window-and-two-pointers/rl0ncs/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路分析

• 今天的算法题目是数组题目，我们解决数组题目常见的思路是排序，指针。题目要求我们找到最长且 连续递增的子序列，返回该序列的长度。

• 这个题目我们无须排序，采用双指针的方式解决。题目已经定义了连续子序列。其中的关键词是 连续 和 递增。在遍历的时候，如果当前遍历到的元素比它左边的那一个元素要严格大，「连续递增」的长度就加 1。否则，需要移动左边元素的位置。实现代码如下，供参考。

通过代码

  class Solution {    public int findLengthOfLCIS(int[] nums) {        int n = nums.length;        int left = 0;        int right = 0;        int ans = 0;        while (right < n) {            if (right > 0 && nums[right - 1] >= nums[right]) {                left = right;            }            ans = Math.max(ans, right - left + 1);            right++;        }
        return ans;    }}

总结

• 上述算法的时间复杂度是 O(n),空间复杂度是 O(1)

• 坚持算法每日一题，加油！