674.最长连续递增序列

(Updated: )
LeetCode

Q

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

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

A

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        //存放最大的递增子序列长度
        int ans = 0;
        int n = nums.length;
        //记录每一个新的递增子序列的起始位置
        int start = 0;
        for (int i = 0; i < n; i++) {
            //如果递增中断，记录新的子序列起始位置
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            //比较当前序列和历史最长递增子序列的长度
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}

  • 思路
    对于下标范围 [l,r] 的连续子序列，如果对任意 l≤i<r 都满足 nums[i]<nums[i+1]，则该连续子序列是递增序列。
    假设数组 nums 的长度是 n，对于 0<l≤r<n−1，如果下标范围 [l,r] 的连续子序列是递增序列，则考虑 nums[l−1] 和 nums[r+1]。
    如果 nums[l−1]<nums[l]，则将 nums[l−1] 加到 nums[l] 的前面，可以得到更长的连续递增序列.
    如果 nums[r+1]>nums[r]，则将 nums[r+1] 加到 nums[r] 的后面，可以得到更长的连续递增序列。
    基于上述分析可知，为了得到最长连续递增序列，可以使用贪心的策略得到尽可能长的连续递增序列。做法是使用记录当前连续递增序列的开始下标和结束下标，遍历数组的过程中每次比较相邻元素，根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标。
    具体而言，令 start 表示连续递增序列的开始下标，初始时 start=0，然后遍历数组 nums，进行如下操作。
    如果下标 i>0 且 nums[i]≤nums[i−1]，则说明当前元素小于或等于上一个元素，因此 nums[i−1] 和 nums[i] 不可能属于同一个连续递增序列，必须从下标 i 处开始一个新的连续递增序列，因此令 start=i。如果下标 i=0 或 nums[i]>nums[i−1]，则不更新 start 的值。
    此时下标范围 [start,i] 的连续子序列是递增序列，其长度为 i−start+1，使用当前连续递增序列的长度更新最长连续递增序列的长度。
    遍历结束之后，即可得到整个数组的最长连续递增序列的长度。

  • 时间复杂度
    O(N)

  • 空间复杂度
    O(1)