[LC674] Longest Continuous Increasing Subsequence
Tuesday, January 15, 2019
这道算法题来自 LeetCode #674:求出无序数组中连续递增子数组的最长长度,相当于 LC3 Longest Substring Without Repeating Characters 基础版本。这里我们同样使用到滑动窗口,那么,这个滑动窗口的长度就是所求的最长长度。
分别设置滑动窗口的左界 $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)$