LeetCode 题解工作台
检测相邻递增子数组 I
给你一个由 n 个整数组成的数组 nums 和一个整数 k ，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b ( a ) 开始的 两个 子数组，并满足下述全部条件： 这两个子数组 nums[a..a + k - 1] 和 nums[b.…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
根据题目描述，我们只需要找到最大的相邻递增子数组长度 ，如果 $\textit{mx} \ge k$，则说明存在两个相邻且长度为 的严格递增子数组。 我们可以使用一次遍历来计算 。具体来说，我们维护三个变量，其中 和 分别表示当前递增子数组的长度和前一个递增子数组的长度，而 表示最大的相邻递增子数组长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个由 n 个整数组成的数组 nums 和一个整数 k，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
- 这两个子数组
nums[a..a + k - 1]和nums[b..b + k - 1]都是 严格递增 的。 - 这两个子数组必须是 相邻的，即
b = a + k。
如果可以找到这样的 两个 子数组，请返回 true；否则返回 false。
子数组 是数组中的一个连续 非空 的元素序列。
示例 1：
输入：nums = [2,5,7,8,9,2,3,4,3,1], k = 3
输出：true
解释：
- 从下标
2开始的子数组为[7, 8, 9]，它是严格递增的。 - 从下标
5开始的子数组为[2, 3, 4]，它也是严格递增的。 - 两个子数组是相邻的，因此结果为
true。
示例 2：
输入：nums = [1,2,3,4,4,4,4,5,6,7], k = 5
输出：false
提示：
2 <= nums.length <= 1001 <= 2 * k <= nums.length-1000 <= nums[i] <= 1000
解题思路
方法一：一次遍历
根据题目描述，我们只需要找到最大的相邻递增子数组长度 ，如果 ，则说明存在两个相邻且长度为 的严格递增子数组。
我们可以使用一次遍历来计算 。具体来说，我们维护三个变量，其中 和 分别表示当前递增子数组的长度和前一个递增子数组的长度，而 表示最大的相邻递增子数组长度。
每当遇到一个非递增的位置时，我们就更新 ，并将 赋值给 ，然后将 重置为 ，其中 的更新方式为 ，即相邻递增子数组来自于当前递增子数组的一半长度，或者前一个递增子数组和当前递增子数组的较小值。
最后，我们只需要判断 是否大于等于 即可。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
mx = pre = cur = 0
for i, x in enumerate(nums):
cur += 1
if i == len(nums) - 1 or x >= nums[i + 1]:
mx = max(mx, cur // 2, min(pre, cur))
pre, cur = cur, 0
return mx >= k
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is processed once while tracking increasing sequences. Space complexity is O(n) in the worst case to store valid subarray starting indices, but can be reduced by checking adjacency on the fly. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting array traversal without nested loops
- question_mark
Looking for handling of overlapping subarrays correctly
- question_mark
Checking for attention to edge cases like k near n/2
常见陷阱
外企场景- error
Confusing non-strictly increasing sequences as valid
- error
Not handling overlapping subarrays correctly
- error
Using nested loops leading to unnecessary O(n*k) complexity
进阶变体
外企场景- arrow_right_alt
Detect adjacent decreasing subarrays of length k
- arrow_right_alt
Find three consecutive increasing subarrays
- arrow_right_alt
Check for subarrays with at least k increasing elements