LeetCode 题解工作台
最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列 ，并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r （ l ）确定，如果对于每个 l ，都有 nums[i] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] …
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们可以遍历数组 ，用变量 记录当前连续递增序列的长度。初始时 $cnt = 1$。 然后，我们从下标 $i = 1$ 开始，向右遍历数组 。每次遍历时，如果 $nums[i - 1] < nums[i]$，则说明当前元素可以加入到连续递增序列中，因此令 $cnt = cnt + 1$，然后更新答案为 $ans = \max(ans, cnt)$。否则，说明当前元素无法加入到连续递增序列中，因此…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 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
解题思路
方法一：一次遍历
我们可以遍历数组 ，用变量 记录当前连续递增序列的长度。初始时 。
然后，我们从下标 开始，向右遍历数组 。每次遍历时，如果 ，则说明当前元素可以加入到连续递增序列中，因此令 ，然后更新答案为 。否则，说明当前元素无法加入到连续递增序列中，因此令 。
遍历结束后，返回答案 即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
ans = cnt = 1
for i, x in enumerate(nums[1:]):
if nums[i] < x:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for an understanding of array traversal and state tracking.
- question_mark
Check for proper handling of edge cases like repeated elements or single-element arrays.
- question_mark
Evaluate the candidate’s ability to implement a solution with O(N) time complexity and O(1) space complexity.
常见陷阱
外企场景- error
Forgetting to reset the current subsequence length after encountering a non-increasing element.
- error
Misunderstanding that the subsequence must be strictly increasing, not just increasing or equal.
- error
Not considering edge cases, such as arrays where all elements are the same or have only one element.
进阶变体
外企场景- arrow_right_alt
Find the longest decreasing subsequence instead of an increasing one.
- arrow_right_alt
Find the longest increasing subsequence with a given maximum allowed difference between consecutive elements.
- arrow_right_alt
Handle multiple subarrays and return the sum of the lengths of all increasing subsequences.