3350. Adjacent Increasing Subarrays Detection II

Leetcode link

题目简介

本题是 3349 的变体

题目一样给的是数字数组 nums，这次需要我们把 k 求出来

/**
 * @param {number[]} nums
 * @return {number}
 */

题目要求我们从 nums 中找出两个等长递增子数组，并且要求我们返回这个长度的最大值 k

解题思路

本题的难点有两个：

1. 如何找出递增子数组的长度
2. 如何通过对比计算出最长的子数组长度

第一个难点我们可以用滑动窗口来求解：我们可以定义一个 left 代表窗口的左边界、right 代表窗口的右边界

此时 right 能够增加的条件就是 right+1 < nums.length && nums[right+1] > nums[right]（right 没有触碰到数组边界且其下一个元素比当前元素大）

当我们确定了 right 之后，我们可以用 right - left + 1 来确定一个递增子数组的长度

为了计算最长子数组长度，我们可以通过一个变量 res 来保存当前的最长子数组长度，一开始为 1

res 的值由两个部份决定：

1. 当前求得的最长子数组长度的一半（将一个递增子数组平均的拆成两个）
2. 当前找到的最长子数组的长度，以及上一次找到最长子数组长度中最小的那一个（为了满足题目条件，长的需要配合短的）

于是我们可以得到 res = max(res, curSubLen >> 1, min(curSubLen, prevSubLen))

其中 curSubLen 代表当前找到的递增子数组长度，prevSubLen 代表上一次找到的最长子数组长度

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxIncreasingSubarrays = function (nums) {
    const len = nums.length
    let prevSubLen = 1
    let left = 0
    let res = 0

    while (left < len) {
        let right = left

        while (right + 1 < len && nums[right] < nums[right + 1]) {
            right++
        }
        const curSubLen = right - left + 1

        res = Math.max(res, curSubLen >> 1, Math.min(curSubLen, prevSubLen))
        prevSubLen = curSubLen
        left = right + 1
    }
    return res
};