674-最长连续递增序列

布满荆棘的人生 2022-01-14 11:21 313阅读 0赞

题目描述

  1. 给定一个未经排序的整数数组，找到最长且连续的的递增序列。

示例 1:

  1. 输入: [1,3,5,4,7]
  2. 输出: 3
  3. 解释: 最长连续递增序列是 [1,3,5], 长度为3。
  4. 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 
  5. 示例 2:
  7. 输入: [2,2,2,2,2]
  8. 输出: 1
  9. 解释: 最长连续递增序列是 [2], 长度为1。
  10. 注意：数组长度不会超过10000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence

解题思路

  • 首先尝试暴力枚举，最坏复杂度接近O(N^2)

    class Solution {

    1. public int findLengthOfLCIS(int[] nums) {
    2.     int max_len = 0;
    3.     for(int i = 0; i < nums.length;i++){
    4.         int len = 1;
    5.         for(int j = i; j < nums.length - 1;j++){
    6.             if(nums[j+1] > nums[j])
    7.                 len++;
    8.             else{
    9.                 i = j;
    10.                 break;
    11.             }
    12.         }
    13.         if(len > max_len)
    14.             max_len = len;
    15.     }
    16.     return max_len;
    18. }

    }

  • 对枚举进行一定改进，让其复杂度接近线性

    class Solution {
    public int findLengthOfLCIS(int[] nums) {

    1.     if(nums.length == 0)
    2.         return 0;
    3.     int max_len = 1,len = 1;
    4.     for(int i = 0; i < nums.length - 1;i++){
    5.         if(nums[i + 1] > nums[i])
    6.             len++;
    7.         else
    8.             len = 1;
    9.         max_len = Math.max(max_len, len);
    10.     }
    11.     return max_len;
    13. }

    }

发表评论

表情：
评论列表 （有 0 条评论，313人围观）

还没有评论，来说两句吧...

相关阅读