最长连续升序子串

11月3日面试题

题目

一个数组，找到其最长的连续升序子串。
例如：数组{1,3,5,4,7}，结果：3。最长的连续升序子串是{1,3,5}。

问题一，返回最长的连续升序子串的长度(LeetCode674. 最长连续递增序列)

解析

从数组nums一个下标i开始，向后寻找nums[j]>nums[j-1]所有元素，直达某一个下标j，此时nums[j]<=nums[j-1]为止，i和j直接的元素就是一个升序的子串，统计记录这个长度是否遍历到的最大值，如果是最大值，记录下来。因为nums[j]<=nums[j-1]，所以j之前的元素开始不会再产生更长的增序子串，而且增序子串一定不再包括j-1和j，i从j开始继续重复上面的步骤，直到数组nums遍历完成。

代码

public int findLengthOfLCIS(int[] nums) {
    if(null == nums || nums.length == 0){
        return 0;
    }
    int result = 0;
    for(int i = 0;i < nums.length;){
        int j = i + 1;
        while(j < nums.length && nums[j] > nums[j-1]){
            j++;
        }
        result = (j - i) > result ? (j - i) : result;
        i = j;
    }
    return result;
}

问题二，返回最长的连续升序子串所有元素，也就是打印这个最长的连续升序子串

解析

与上面问题一的解析思路一样，不同之处就是需要多定义两个变量记录下这个最长连续升序子串的起始和结束位置。

代码

//返回长度为2的数组，记录着最长的连续升序子串的开始下标和结束下标
public int[] findLengthOfLCIS(int[] nums) {
    if(null == nums || nums.length == 0){
        return 0;
    }
    int result = 0;
    //长度为2的数组
    int[] arr = {0, 0};
    for(int i = 0;i < nums.length;){
        int j = i + 1;
        while(j < nums.length && nums[j] > nums[j-1]){
                j++;
        }
        //记录最长的连续升序子串的开始下标和结束下标
        if((j - i) > result){
            result = j - i;
            arr[0] = i;
            arr[1] = j;
        }
        i = j;
    }
    //返回最长的连续升序子串的开始下标和结束下标，调用者进行子串的打印
    return arr;
}