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

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

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈

今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

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] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 
1
2
3
4

示例 2：

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

提示：

• 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& 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; //返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12

3.2 🚀 细节解析

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

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

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

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

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

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

四 🏠 心路历程

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

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

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

 int findLengthOfLCIS(vector& 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;//记录下开始位置
         } else if (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; //处理无递增序列的特殊情况
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪