3349. 检测相邻递增子数组 I

题目描述

给你一个由 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 <= 100
1 <= 2 * k <= nums.length
-1000 <= nums[i] <= 1000

解法

方法一：一次遍历

根据题目描述，我们只需要找到最大的相邻递增子数组长度 \(\textit{mx}\)，如果 \(\textit{mx} \ge k\)，则说明存在两个相邻且长度为 \(k\) 的严格递增子数组。

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

每当遇到一个非递增的位置时，我们就更新 \(\textit{mx}\)，并将 \(\textit{cur}\) 赋值给 \(\textit{pre}\)，然后将 \(\textit{cur}\) 重置为 \(0\)，其中 \(\textit{mx}\) 的更新方式为 \(\textit{mx} = \max(\textit{mx}, \lfloor \frac{\textit{cur}}{2} \rfloor, \min(\textit{pre}, \text{cur}))\)，即相邻递增子数组来自于当前递增子数组的一半长度，或者前一个递增子数组和当前递增子数组的较小值。

最后，我们只需要判断 \(\textit{mx}\) 是否大于等于 \(k\) 即可。

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

Python3JavaC++GoTypeScriptRustJavaScript

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

class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int mx = 0, pre = 0, cur = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            ++cur;
            if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {
                mx = Math.max(mx, Math.max(cur / 2, Math.min(pre, cur)));
                pre = cur;
                cur = 0;
            }
        }
        return mx >= k;
    }
}

class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        int mx = 0, pre = 0, cur = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            ++cur;
            if (i == n - 1 || nums[i] >= nums[i + 1]) {
                mx = max({mx, cur / 2, min(pre, cur)});
                pre = cur;
                cur = 0;
            }
        }
        return mx >= k;
    }
};

func hasIncreasingSubarrays(nums []int, k int) bool {
    mx, pre, cur := 0, 0, 0
    for i, x := range nums {
        cur++
        if i == len(nums)-1 || x >= nums[i+1] {
            mx = max(mx, max(cur/2, min(pre, cur)))
            pre, cur = cur, 0
        }
    }
    return mx >= k
}

function hasIncreasingSubarrays(nums: number[], k: number): boolean {
    let [mx, pre, cur] = [0, 0, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            mx = Math.max(mx, (cur / 2) | 0, Math.min(pre, cur));
            [pre, cur] = [cur, 0];
        }
    }
    return mx >= k;
}

impl Solution {
    pub fn has_increasing_subarrays(nums: Vec<i32>, k: i32) -> bool {
        let n = nums.len();
        let (mut mx, mut pre, mut cur) = (0, 0, 0);

        for i in 0..n {
            cur += 1;
            if i == n - 1 || nums[i] >= nums[i + 1] {
                mx = mx.max(cur / 2).max(pre.min(cur));
                pre = cur;
                cur = 0;
            }
        }

        mx >= k
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var hasIncreasingSubarrays = function (nums, k) {
    const n = nums.length;
    let [mx, pre, cur] = [0, 0, 0];
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            mx = Math.max(mx, cur >> 1, Math.min(pre, cur));
            pre = cur;
            cur = 0;
        }
    }
    return mx >= k;
};

3349. 检测相邻递增子数组 I

题目描述

解法

方法一：一次遍历

评论