leetcode🧑‍💻 674. 最长连续递增序列

2022-07-11 | 2024-03-15 | 559 | 2 分钟

最长连续递增序列

双指针滑动窗口

解题思路：
- 初始化声明 left、right 指针，res 最大长度；
- 只要是递增序列，right 就一直向右移动，计算 left 和 right 的最大窗口；
- 如果是非递增，则 left = right，right 继续向右移动判断之后的序列是否是递增；
- 最后将结果返回；
图解：
复杂度：
- 时间复杂度：O(n)；
- 空间复杂度：状态压缩之前是 O(1)；

代码实现：

var findLengthOfLCIS = function (nums) {
  let left = 0;
  let right = 1;
  let res = 1;

  while (right < nums.length) {
    // 非递增，此时窗口大小为 0
    if (nums[right - 1] >= nums[right]) {
      left = right;
    }

    // 递增，right 向右移动
    right++;
    // 更新窗口最大值
    res = Math.max(res, right - left);
  }

  return res;
};

动态规划

解题思路：
- 以数组 [1,3,5,4,7,8,9,2] 为例，图表上每一个点即代表数组中的每一个数；
- 本题求 “最长连续递增” 子序列的长度，也就是收集图中所有上坡片段的长度，最后取最大值即可；
复杂度：
- 时间复杂度：O(n)；
- 空间复杂度：状态压缩之前是 O(n)，状态压缩后是 O(1)；

代码实现：

var findLengthOfLCIS = function (nums) {
  // 初始化数组dp,每个索引所对应的值均为1
  let dp = new Array(nums.length).fill(1);

  // 从索引 1 的位置开始遍历，若后一个元素 大于 前一个元素，则 dp[i] = dp[i - 1] + 1; 
  // 递减则不做任何操作,相当于dp[i] = 1
  for (var i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      dp[i] = dp[i - 1] + 1;
    }
  }

  // dp = [1, 2, 3, 1, 2, 3, 4, 1]，取最大值4
  return Math.max(...dp);
};

贪心

解题思路：
- 通过收集所有上坡片段的长度，取其中最大值；
- 贪心的角度是通过比较局部的最优解，最终得到全局的最优解；
图解：
复杂度：
- 时间复杂度：O(n)；
- 空间复杂度：状态压缩之前是 O(n)，状态压缩后是 O(1)；

代码实现：

var findLengthOfLCIS = function (nums) {
  let res = 1,
    max = 1;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      res++;
    } else {
      res = 1;
    }
    max = Math.max(max, res);
  }
  
  return max;
};

扫码领红包

您的打赏是我前进的动力

微信

支付宝

算法基础🔮 分治基础

392.判断子序列

中午好👏🏻，我是 ✍🏻 疯狂 codding 中...

粽子

这有关于产品、设计、开发的问题和看法，还有技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程

了解更多

1. 最长连续递增序列
2. 双指针滑动窗口
3. 动态规划
4. 贪心