LeetCode: 最长连续递增序列
2019-02-14 本文已影响26人
一萍之春
最长连续递增序列
题目叙述:
给定一个未经排序的整数数组,找到最长且连续的的递增序列。
示例1:
输入: [1,3,5,4,7]
输出: 3
解释:最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为5和7在原数组里被4隔开。
示例2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
解题思路:
因为需要查找出最长的连续递增序列,这是一个很明显的一维dp问题也就是常说的一维动态规划问题,数组nums[]中第i个元素比它的前一个大的话到i的递增序列长度就是i-1的cnt加1,如果小于或者等于i-1个元素的话序列的长度cnt累加要重新从1开始累加。每当cnt被重置时以及返回结果前和cnt和max进行比较也就是max=max<cnt?cnt:max;
时间复杂度为O(n),空间复杂度为O(1);
实现代码:
class Solution {
public int findLengthOfLCIS(int[] nums) {
int len=nums.length;
//数组长度比2小的直接返回数组长度即可
if(len<2){
return len;
}
int max=1,cnt=1;
for(int i=1;i<len;++i){
if(nums[i]>nums[i-1]){
cnt++;
}else{
max=max<cnt?cnt:max;
cnt=1;
}
}
return max<cnt?cnt:max;
}
}