主要思路:用两个指针分别指向子串的开头和结尾,分别找到两个子串的结束位置。然后根据两个子串之间的关系来更新最长子串的长度。 具体实现: 1.如果数组长度小于等于0,则返回0。 2.初始化变量res为0,start1和end1指针都指向数组的第一个元素。 3.首先找到第一个子串的结尾位置end1,在子串严格递增时一直向后移动end1指针。 4.如果发现整个数组是严格递增的,则直接返回整个数组的长度。 5.接下来寻找另一个子串的开始位置start2,从end1+1开始,然后找到这个子串的结尾位置end2,同样也是在子串严格递增的情况下一直向后移动end2指针。 6.然后分别判断两个子串之间的关系,并根据不同的情况来更新最长子串的长度: ①如果两个子串之间不存在空隙,则直接更新最长子串的长度,即res=max(res,end2-start2+end1-start1+2)。 ②如果两个子串之间有空隙,则更新最长子串的长度为两个子串中长度最长的那个加上1,即res=max(res,max(end2-start2,end1-start1)+2)。 7.最后更新start1和end1指针为start2和end2,继续寻找下一个符合条件的子串,直到end1指向数组的最后一个元素为止。 8.返回最长子串长度res即可。 时间复杂度:O(n)
点赞

相关推荐

想润的芹菜人狠话不多:把其中一个老总放中间都会得罪另一个
点赞 评论 收藏
分享
牛客网
牛客企业服务