本文主要是介绍【LeetCode】674. 最长连续递增序列(简单)——代码随想录算法训练营Day52,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:
题目描述
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l
和 r
(l < r
)确定,如果对于每个 l <= i < r
,都有 nums[i] < nums[i + 1]
,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
就是连续递增子序列。
示例 1:
输入:nums = [1,3,5,4,7] 输出:3 解释:最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。
示例 2:
输入:nums = [2,2,2,2,2] 输出:1 解释:最长连续递增序列是 [2], 长度为1。
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
文章讲解:代码随想录
视频讲解:动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列_哔哩哔哩_bilibili
题解1:贪心算法
思路:取更长的连续子序列为局部最优,全局最优为最长连续子序列。
/*** @param {number[]} nums* @return {number}*/
var findLengthOfLCIS = function(nums) {let res = 1;let temp = 1;for (let i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {temp++;if (temp > res) {res = temp;}} else {temp = 1;}}return res;
};
分析:时间复杂度为 O(n),空间复杂度为 O(1)。
题解2:动态规划
思路:使用动态规划法求解子序列问题。
动态规划分析:
- dp 数组以及下标的含义:dp[i] 代表以 nums[i] 结尾的最长递增子序列的长度。
- 递推公式:nums[i] 大于 nums[i - 1] 时,dp[i] = dp[i - 1] + 1。
- dp 数组初始化:全部初始化为1。
- 遍历顺序:从前到后。
- 打印 dp 数组:以输入 [1,3,5,4,7] 为例,dp 数组为 [ 1, 2, 3, 1, 2 ]。
/*** @param {number[]} nums* @return {number}*/
var findLengthOfLCIS = function(nums) {const dp = new Array(nums.length).fill(1);for (let i = 1; i < nums.length; i++) {dp[i] = nums[i] > nums[i - 1] ? dp[i - 1] + 1 : 1;}return Math.max(...dp);
};
分析:时间复杂度为 O(),空间复杂度为 O()。
收获
练习动态规划法求解子序列问题,注意本题为连续子序列。
这篇关于【LeetCode】674. 最长连续递增序列(简单)——代码随想录算法训练营Day52的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!