刷爆力扣之最长连续递增序列

简介: 刷爆力扣之最长连续递增序列

一 🏠 题目描述

674. 最长连续递增序列


给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。


连续递增的子序列 可以由两个下标 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] 也是升序的子序列, 但它不是连续的,因为 57 在原数组里被 4 隔开。 

示例 2:


输入:nums = [2,2,2,2,2]
输出:1
解释:最长连续递增序列是 [2], 长度为1。

提示:


1 <= nums.length <=104-109 <= nums[i] <=109


二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎


一个未经排序的数组,找到最长且 连续递增的子序列,并返回该序列的长度


看到连续就应该联想到前者比较后者的逻辑,递增规定了序列的比较条件 🌹🌹🌹



提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃



2.2 🚀 思路整理

贪心法


使用贪心策略得到尽可能长的连续递增序列


记录当前连续递增序列开始下标和结束下标,遍历数组的过程中每次比较相邻元素,根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标 🌺🌺🌺



具体流程,令 start 表示连续递增序列的开始下标,初始时 start = 0,然后遍历数组 nums,进行如下操作


① 如果下标 i > 0 且 nums[i−1] >= nums[i],则说明当前元素小于或等于上一个元素,因此 nums[i−1] 和 nums[i] 不属于同一个连续递增序列,必须从下标 i 处开始一个新的连续递增序列,因此令 start=i。


② 如果下标 i = 0 或 nums[i] > nums[i−1],则不更新 start 的值。此时下标范围 [start , i] 的连续子序列是递增序列,其长度为 i − start + 1,使用当前连续递增序列的长度更新最长连续递增序列的长度


遍历结束之后,即可得到整个数组的最长连续递增序列的长度 🌺🌺🌺



🌸🌸🌸


整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃



三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路,直接代码走起来 👇👇👇👇


int findLengthOfLCIS(std::vector<int>& nums) {
    int res =0; //定义最长且连续递增的子序列
    int n = nums.size(); //获取输入数组长度
    int start=0; //定义连续递增子序列的起始索引
for (int i =0; i < n; i++) {  //遍历数组
if (i > 0 && nums[i -1] >= nums[i]) {  //i > 0, 处理 i =0 特殊情况(仅一个元素)
start= i; //当出现不满足连续递增情况时, 更新 start        }
        res = max(res, i -start+1);  //不断更新连续递增子序列长度
    }
    return res; //返回结果
}


3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃


那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析,直接开干,走起来 👇👇👇👇


if (i > 0 && nums[i -1] >= nums[i]) ... //处理 i =0 特殊情况

判决条件中的 i > 0 处理了 i = 0 的特殊情况 🐌🐌🐌



res = max(res, i -start+1);  //不断更新连续递增子序列长度

不断获取最优解是贪心算法的核心点,常规解决方式需要判断结尾特殊情况,而该实现很巧妙的将对序列遍历过程的操作进行了统一,代码很简洁 🐳🐳🐳



四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程,我把当时状态纯纯真实还原,记录在心路历程这一小节,不感兴趣的小伙伴可以直接跳过哈


博主在第一阶段提取 🚀 关键信息没有问题,在第二阶段 🚀 思路整理未联想到贪心算法


代码实现使用了常规解法,代码效率还 OK,但简洁性差 😭😭😭 ,代码如下 👇👇👇👇


int findLengthOfLCIS(vector<int>& nums) {
     int startIndex =-1, res =0, len = nums.size();
for (int i =1; i < len; ++i) { //从 1- len 遍历数组
if (nums[i -1] < nums[i] && startIndex ==-1) { //如果前一个小于后一个且为递增序列的开始
             startIndex = i -1;//记录下开始位置
         } elseif (nums[i -1] >= nums[i] && startIndex !=-1) { //如果前一个大于等于后一个且为递增序列的结束
             res = std::max(res, i - startIndex); //记录下递增序列的长度
             startIndex =-1; //并将起始位置重新置为 0         } 
if (nums[i -1] < nums[i] && i == len -1) { // 结尾一批数据的输出
             res = std::max(res, i - startIndex +1); //记录下递增序列的长度
         }
     }
     return res ==0 ? 1 : res; //处理无递增序列的特殊情况
 }
相关文章
|
3月前
|
Python
【Leetcode刷题Python】376. 摆动序列
文章提供了解决LeetCode "摆动序列" 问题的Python实现代码,通过遍历整数数组并使用两个变量 down 和 up 来记录正差和负差摆动序列的长度,最终返回最长摆动子序列的长度。
39 0
|
3月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
28 6
|
3月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
22 3
|
3月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现,通过递归方法根据前序和中序遍历序列重建二叉树。
24 3
|
3月前
|
算法 Python
【Leetcode刷题Python】300. 最长递增子序列
LeetCode 300题 "最长递增子序列" 的两种Python解决方案:一种使用动态规划,另一种使用贪心算法结合二分查找。
34 1
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
40 0
|
3月前
|
Python
【Leetcode刷题Python】674. 最长连续递增序列
LeetCode 674题 "最长连续递增序列" 的Python解决方案,使用动态规划算法找出给定整数数组中最长连续递增子序列的长度。
90 0
|
5月前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
5月前
|
Java
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
|
5月前
|
存储 算法
力扣经典150题第四十六题:最长连续序列
力扣经典150题第四十六题:最长连续序列
24 0