3350、[中等] 检测相邻递增子数组 Ⅱ
1、题目描述
给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增
子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
- 这两个子数组
nums[a..a + k - 1]和nums[b..b + k - 1]都是 严格递增 的。 - 这两个子数组必须是 相邻的，即
b = a + k。
返回 k 的 最大可能 值。
子数组 是数组中的一个连续 非空 的元素序列。
2、解题思路
在给定问题中，我们的目标是寻找两个相邻且严格递增的子数组，并且最大化长度 𝑘。当前的超时可能由于在每个候选长度 k 上都逐一检查数组所致。为此，我们可以对每个元素的递增情况进行一次遍历，预处理连续的递增段信息，然后利用这些信息来快速验证长度为 k 的相邻递增子数组是否存在。
-
递增段预处理：
-
预先处理 nums 中每个位置 i 的最长递增序列长度 increasing_lengths[i]，表示从位置 i 开始的最长递增序列的长度。
-
通过一次遍历即可获取此信息。
-
-
二分查找确定最大 𝑘 ：
- 使用二分查找寻找最大的 k 值。对于每个候选长度 k，快速判断是否存在相邻且严格递增的子数组。
- 在判断过程中，利用 increasing_lengths 数组来验证：如果位置 i 的递增序列长度 increasing_lengths[i] ≥ k 且位置 i + k 的递增序列长度 increasing_lengths[i + k] ≥ k，则位置 i 和 i + k 可以构成所需的相邻递增子数组。
3、代码实现
class Solution {
public:int maxIncreasingSubarrays(vector<int>& nums) {int n = nums.size();// 预处理递增段长度vector<int> increasing_lengths(n, 1);for (int i = n - 2; i >= 0; --i) {if (nums[i] < nums[i + 1]) {increasing_lengths[i] = increasing_lengths[i + 1] + 1;}}// 二分查找确定最大 k 值int low = 1, high = n / 2;int maxK = 0;while (low <= high) {int mid = low + (high - low) / 2;bool found = false;// 检查是否存在两个长度为 mid 的相邻递增子数组for (int i = 0; i + 2 * mid - 1 < n; ++i) {if (increasing_lengths[i] >= mid &&increasing_lengths[i + mid] >= mid) {found = true;break;}}if (found) {maxK = mid;low = mid + 1;} else {high = mid - 1;}}return maxK;}
};
4、复杂度
-
时间复杂度: 预处理 increasing_lengths 数组的复杂度为 O(n)。二分查找过程的复杂度为 O(logn)，对于每个候选长度 k，只需 O(n) 的时间验证是否存在符合条件的相邻子数组。因此总复杂度为 O(nlogn)。
-
空间复杂度: O(n)，用于存储 increasing_lengths 数组。