[LC674] Longest Continuous Increasing Subsequence

Tuesday, January 15, 2019

这道算法题来自 LeetCode #674:求出无序数组中连续递增子数组的最长长度,相当于 LC3 Longest Substring Without Repeating Characters 基础版本。这里我们同样使用到滑动窗口,那么,这个滑动窗口的长度就是所求的最长长度。

sliding window [i, j]

分别设置滑动窗口的左界 $j$ 和右界 $i$;初始状态时,$i$ 从第二个元素开始,即 $i = 1$,从左向右移动。对于 $i$,每当移动一步之后,计算滑动窗口的长度,即 $length = i - j + 1$;每当遇到当前的元素没有比上一个元素大,即 $element_{i - 1} >= element_{i}$,则把 $j$ 移动到 $i$ 所在的位置,然后重新计算窗口的长度。

反复上述操作,直到 $i$ 抵达最后一个元素,此时,从这一组 $length$ 中选出最大者即所求的最长长度。

Implementation

function findLengthOfLCIS(nums) {
  if (!nums) {
    return 0
  }
  
  if (nums.length < 2) {
    return nums.length;
  }
  
  let maxLength = 1
  let j = 0
  
  for (let i = 1; i <= nums.length; i++) {
    if (nums[i - 1] >= nums[i]) {
      j = i
    }
    
    maxLength = Math.max(maxLength, i - j + 1)
  }
  
  return maxLength
}

复杂度分析

对于数组长度为 $n$ 的数组,

  • 时间复杂度:由于每个元素只会遍历一次,所以时间复杂度为 $O(n)$