0674-最长连续递增序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

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

方法一：贪心

对于下标范围 [l,r] 的连续子序列，如果对任意 l \le i<r 都满足 nums}[i]<\textit{nums}[i+1]，则该连续子序列是递增序列。

假设数组 nums 的长度是 n，对于 0<l \le r<n-1，如果下标范围 [l,r] 的连续子序列是递增序列，则考虑 nums}[l-1] 和 nums}[r+1]。

  • 如果 nums}[l-1]<\textit{nums}[l]，则将 nums}[l-1] 加到 nums}[l] 的前面，可以得到更长的连续递增序列.

  • 如果 nums}[r+1]>\textit{nums}[r]，则将 nums}[r+1] 加到 nums}[r] 的后面，可以得到更长的连续递增序列。

基于上述分析可知，为了得到最长连续递增序列，可以使用贪心的策略得到尽可能长的连续递增序列。做法是使用记录当前连续递增序列的开始下标和结束下标，遍历数组的过程中每次比较相邻元素，根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标。

具体而言，令 start 表示连续递增序列的开始下标，初始时 start}=0，然后遍历数组 nums，进行如下操作。

  • 如果下标 i>0 且 nums}[i] \le \textit{nums}[i-1]，则说明当前元素小于或等于上一个元素，因此 nums}[i-1] 和 nums}[i] 不可能属于同一个连续递增序列，必须从下标 i 处开始一个新的连续递增序列，因此令 start}=i。如果下标 i=0 或 nums}[i]>\textit{nums}[i-1]，则不更新 start 的值。

  • 此时下标范围 [\textit{start},i] 的连续子序列是递增序列，其长度为 i-\textit{start}+1，使用当前连续递增序列的长度更新最长连续递增序列的长度。

遍历结束之后，即可得到整个数组的最长连续递增序列的长度。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var findLengthOfLCIS = function(nums) {
    let ans = 0;
    const n = nums.length;
    let start = 0;
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            start = i;
        }
        ans = Math.max(ans, i - start + 1);
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findLengthOfLCIS(nums []int) (ans int) {
    start := 0
    for i, v := range nums {
        if i > 0 && v <= nums[i-1] {
            start = i
        }
        ans = max(ans, i-start+1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = max(ans, i - start + 1);
        }
        return ans;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
int findLengthOfLCIS(int* nums, int numsSize) {
    int ans = 0;
    int start = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            start = i;
        }
        ans = fmax(ans, i - start + 1);
    }
    return ans;
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        start = 0

        for i in range(n):
            if i > 0 and nums[i] <= nums[i - 1]:
                start = i
            ans = max(ans, i - start + 1)
        
        return ans

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次。

  • 空间复杂度：O(1)。额外使用的空间为常数。

 Comments
On this page
0674-最长连续递增序列