滑动窗口
解题思路
声明 res 记录结果， left 为滑动窗口的左边界、right 为滑动窗口的右边界；
迭代 nums 数组，
- 如果当前元素 大于 前一个元素，则满足递增序列，right 向右移动；
- 如果当前元素 小于等于 前一个元素，则不满足递增序列，令 left = right 从 right 继续向右寻找 连续递增序列；
迭代结束后将 res 返回；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
var findLengthOfLCIS = function (nums) {
let res = 1;
let left = 0;
let right = 1;
while (right < nums.length) {
// 如果当前元素 <= 前一个元素，则不满足递增序列，在 right 处继续向右查找
if (nums[right - 1] >= nums[right]) left = right;
// right 向右移动，更新窗口最大值
res = Math.max(res, ++right - left);
}
return res;
};
贪心
解题思路
通过收集所有上坡片段的长度，取其中最大值；
贪心的角度是通过比较局部的最优解，最终得到全局的最优解；
图解
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
var findLengthOfLCIS = function (nums) {
let max = 1;
let res = 1;
for (let i = 1; i < nums.length; i++) {
res = nums[i] > nums[i - 1] ? res + 1 : 1;
max = Math.max(max, res);
}
return max;
};
动态规划
解题思路
确定 dp 数组以及下标的含义：以下标 i 为结尾的连续递增的子序列长度为 dp[i]；
确定递推公式：
- 如果 nums[i] > nums[i - 1] 则说明当前元素符合递增子序列，则 dp[i] = dp[i - 1] + 1；
- 如果 nums[i] <= nums[i - 1] 则说明当前元素不符合递增子序列，则什么都不做；
如何初始化 dp 数组：将 dp 全部初始化为 1；
确定遍历顺序：从递推公式上可以看出， dp[i] 依赖 dp[i - 1]，所以一定是从前向后遍历；
举例推导 dp 数组：以 nums = [1, 3, 5, 4, 7] 为例：
i = 0 i = 1 i = 2 i = 3 i = 4 dp[i] 最长连续递增子序列 1 2 31 2
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：状态压缩之前是
O(n)，状态压缩后是O(1)；
代码实现
var findLengthOfLCIS = function (nums) {
let dp = new Array(nums.length).fill(1);
for (var i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
}
return Math.max(...dp);
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 300. 最长递增子序列
上一篇
评论
