What is the main approach for Adjacent Increasing Subarrays Detection II?

Use binary search over possible lengths k and validate each with a sliding window or precomputed increasing sequences.

How do I efficiently check if a subarray is strictly increasing?

Precompute the lengths of increasing sequences ending at each index to avoid rescanning elements.

What if no adjacent increasing subarrays exist?

Return 0 since no valid k satisfies the problem condition.

Can overlapping subarrays be considered adjacent?

No, adjacent subarrays must be consecutive and non-overlapping.

Why binary search works for this problem?

Because the set of valid k values is monotonic: if k is valid, all smaller lengths are also valid.

#3350

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

检测相邻递增子数组 II

给你一个由 n 个整数组成的数组 nums ，请你找出 k 的最大值，使得存在两个相邻且长度为 k 的严格递增子数组。具体来说，需要检查是否存在从下标 a 和 b ( a ) 开始的两个子数组，并满足下述全部条件：这两个子数组 nums[a..a + k - 1] 和 nums…

数组二分查找

题目描述

给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在两个相邻且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的两个子数组，并满足下述全部条件：

这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
这两个子数组必须是 相邻的，即 b = a + k。

返回 k 的 最大可能 值。

子数组 是数组中的一个连续非空的元素序列。

示例 1：

输入：nums = [2,5,7,8,9,2,3,4,3,1]

输出：3

解释：

从下标 2 开始的子数组是 [7, 8, 9]，它是严格递增的。
从下标 5 开始的子数组是 [2, 3, 4]，它也是严格递增的。
这两个子数组是相邻的，因此 3 是满足题目条件的最大 k 值。

示例 2：

输入：nums = [1,2,3,4,4,4,4,5,6,7]

输出：2

解释：

从下标 0 开始的子数组是 [1, 2]，它是严格递增的。
从下标 2 开始的子数组是 [3, 4]，它也是严格递增的。
这两个子数组是相邻的，因此 2 是满足题目条件的最大 k 值。

提示：

2 <= nums.length <= 2 * 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：一次遍历

我们可以使用一次遍历来计算最大的相邻递增子数组长度 $\textit{ans}$ 。具体地，我们维护三个变量 $\textit{cur}$ 和 $\textit{pre}$ 分别表示当前递增子数组和上一个递增子数组的长度，而 $\textit{ans}$ 表示最大的相邻递增子数组长度。

每当遇到一个非递增的位置时，我们就更新 $\textit{ans}$ ，将 $\textit{cur}$ 赋值给 $\textit{pre}$ ，并将 $\textit{cur}$ 重置为 $0$ 。更新 $\textit{ans}$ 的公式为 $\textit{ans} = \max(\textit{ans}, \lfloor \frac{\textit{cur}}{2} \rfloor, \min(\textit{pre}, \textit{cur}))$ ，表示相邻递增子数组要么来自当前递增子数组长度的一半，要么来自前一个递增子数组和当前递增子数组的较小值。

最后我们只需要返回 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        ans = pre = cur = 0
        for i, x in enumerate(nums):
            cur += 1
            if i == len(nums) - 1 or x >= nums[i + 1]:
                ans = max(ans, cur // 2, min(pre, cur))
                pre, cur = cur, 0
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to binary search on k and linear validation per candidate. Space complexity is O(n) for storing precomputed increasing lengths.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to explain why naive O(n^2) checking fails for large arrays.
question_mark
Look for clear reasoning on using binary search over answer space rather than array indices.
question_mark
Candidate should handle edge cases where no valid adjacent increasing subarrays exist.

warning

常见陷阱

外企场景

error
Off-by-one errors when checking subarray boundaries.
error
Failing to handle overlapping subarrays correctly.
error
Not precomputing increasing lengths, leading to timeout on large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum k for two non-adjacent strictly increasing subarrays.
arrow_right_alt
Determine maximum k for decreasing subarrays instead of increasing.
arrow_right_alt
Return all starting indices of valid adjacent increasing subarrays of maximum length.

help

常见问题

外企场景

继续练习

#3347 执行操作后元素的最高频率 II #3346 执行操作后元素的最高频率 I #3356 零数组变换 II