Skip to content

3350. Adjacent Increasing Subarrays Detection II

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k starting at indices a and b (a < b), where:

  • Both subarrays nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.
  • The subarrays must be adjacent, meaning b = a + k.

Return the maximum possible value of k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [2,5,7,8,9,2,3,4,3,1]

Output: 3

Explanation:

  • The subarray starting at index 2 is [7, 8, 9], which is strictly increasing.
  • The subarray starting at index 5 is [2, 3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 3 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Example 2:

Input: nums = [1,2,3,4,4,4,4,5,6,7]

Output: 2

Explanation:

  • The subarray starting at index 0 is [1, 2], which is strictly increasing.
  • The subarray starting at index 2 is [3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 2 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Constraints:

  • 2 <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109

[2,5,7,8,9,

​ 2,3,4,

​ 3,

​ 1]

数组中 找到两个相邻的子数组[2,5,7,8], [2,3, 4]

问长度最大多少?

两种情况:

  1. 两段长度的最小值 min(5,3)

[2,5,7,8,9] [2,3, 4]

len 5, len 3

  1. [2,5,7,8,9] -> [5, 7] [8,9]

5/2

核心想法: 遍历数组

把每一个递增段的长度找出来 5, 3, 1, 1

然后在根据两种情况进行计算, 最大值就是答案了

https://www.bilibili.com/video/BV1JVmBYvEnD/?spm_id_from=333.999.0.0&vd_source=73e7d2c4251a7c9000b22d21b70f5635